Я в настоящее время пытаюсь реализовать генератор LALR-парсера, как описано в "принципиальных методах и инструментах компиляторов" (также названный "книга дракона").
Много уже работы. Парсер-генератор в настоящее время может генерировать полный goto-график.
Example Grammar:
S' --> S
S --> C C
C --> c C
C --> d
Nonterminals: S', S, C
Terminals: c, d
Start: S'
Goto-график:
I[0]---------------+ I[1]-------------+
| S' --> . S , $ |--S-->| S' --> S . , $ |
| S --> . C C , $ | +----------------+
| C --> . c C , c |
| C --> . c C , d | I[2]--------------+
| C --> . d , c | | S --> C . C , $ | I[3]--------------+
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ |
+------------------+ | C --> . d , $ | +-----------------+
| | +-----------------+
| | +--c--+ | |
| | | | c |
| | | v v |
| | I[4]--------------+ |
| c | C --> c . C , c | |
| | | C --> c . C , d | |
| | | C --> c . C , $ | d
| | | C --> . c C , c | |
| +---->| C --> . c C , d | |
| | C --> . c C , $ | |
d | C --> . d , c |--+ |
| +-----| C --> . d , d | | |
| | | C --> . d , $ | | |
| | +-----------------+ | |
| C | |
| | I[6]--------------+ | |
| | | C --> c C . , c | d |
| +---->| C --> c C . , d | | |
| | C --> c C . , $ | | |
| +-----------------+ | |
| | |
| I[5]------------+ | |
| | C --> d . , c |<---+ |
+------->| C --> d . , d | |
| C --> d . , $ |<-----+
+---------------+
У меня есть trubbles с реализацией алгоритма для генерации таблицы действий! Мой алгоритм вычисляет следующий вывод:
state | action
| c | d | $
------------------------
0 | s4 | s5 |
------------------------
1 | | | acc
------------------------
2 | s4 | s5 |
------------------------
3 | | | r?
------------------------
4 | s4 | s5 |
------------------------
5 | r? | r? | r?
------------------------
6 | r? | r? | r?
sx... смещаются для утверждения x
rx... уменьшают для утверждения x
R? средства, которые я не знаю, как получить состояние (?), до которого синтаксический анализатор должен уменьшить. Кто-либо знает, что алгоритм добирается? использование goto-графика выше?
Если что-нибудь, описывают не достаточно ясно, спросите, и я попытаюсь объяснить это лучше!Спасибо за помощь!