Лексический анализатор и анализатор связи - PullRequest
3 голосов
/ 23 февраля 2012

Большинство ресурсов по лексическим анализаторам и анализаторам иллюстрируют использование потоков для связи между ними (или я так понимаю).

Объясняется, что анализатор запрашивает следующий токен, скажем, путем вызова функцииgetNextToken(), и лексер отвечает на него, возвращая следующий токен.Должны ли мы думать о них как о двух объектах, взаимодействующих в одной и той же программе, или двух разных программах, взаимодействующих через потоки?

Кроме того, я не смог понять, почему не выбран последовательный подход, т.е.лексический анализатор работает до конца предоставленного источника, и только после этого синтаксический анализатор использует выходные данные лексического анализатора для анализа.Если быть точным, если лексический анализатор читает следующую лексему только тогда, когда анализатор запрашивает следующий токен, как обрабатывается ошибка?Особенно, если ошибка возникает в конце файла, все вычисления, выполненные анализатором, могут быть потеряны из-за ошибки (при условии, что очень простой анализатор без каких-либо возможностей обработки ошибок).Кэшируются ли последние результаты?

Ответы [ 2 ]

7 голосов
/ 23 февраля 2012

Мой ответ ниже относится только к модели компиляции Flex-Bison (или Lex-Yacc). У меня мало знаний о других моделях.

Я думаю о комбинации лексер / парсер как о двух взаимодействующих модулях в одной программе. Когда вы используете Flex с Bison, вы видите, что последний вызывает функцию yylex(), предоставленную первым (yylex() эквивалентно функции getNextToken() в вашем вопросе). Поэтому имеет больше смысла думать о них как о взаимодействующих единицах в одной программе, а не двух разных программах. Более того, если бы лексер и парсер были 2 разными программами, вам пришлось бы иметь дело с межпроцессным взаимодействием, общей памятью и связанными с этим проблемами, что еще больше усложняло бы задачу.

Чтобы ответить на ваш второй вопрос: Я могу вспомнить одну важную проблему, которая может возникнуть из-за того, что синтаксический анализатор вступил в действие после , когда лексер завершил чтение всех вводимых данных: использование памяти было бы огромным даже для программ среднего размера, так как вам пришлось бы хранить данные структуры для каждого токена в памяти (представьте, что токены, такие как , и =, занимают несколько байтов в памяти, и вы быстро поймете, почему он не масштабируется).

Что касается обработки ошибок: если лексер не может сопоставить входные данные с каким-либо регулярным выражением, то yylex() должен вернуть -1 в синтаксический анализатор, используя следующее правило:

.               { return -1; }

(Обратите внимание на почти невидимый период в первом столбце, который соответствует любому входному символу, кроме \n)

( ПРИМЕЧАНИЕ : это правило должно быть последним , которое должно отображаться в вашем гибком файле, поскольку порядок правил определяет приоритет: токен сопоставляется Flex с использованием первое возможное правило в файле flex.)

Возвращаемое лексером значение -1 указывает на ошибку токенизации , и синтаксический анализатор Bison обрабатывает ее автоматически, вызывая yyerror(char *) (идеально определяется вами); в противном случае, если на входе возникает ошибка синтаксического анализа , синтаксический анализатор снова вызывает yyerror(char *).

Кроме того, если вы хотите отобразить ошибочный фрагмент кода при обнаружении ошибки, вам потребуется способ доступа к связанному исходному коду с помощью дефектного токена, что означает, что следует полностью придерживаться подхода чтения входных данных. Синтаксический анализ не будет работать вообще, если только вы не сохраните связанный исходный код с каждым токеном во время токенизации, что по существу делает гиганта памяти компилятором.

0 голосов
/ 24 февраля 2012

Большинство ресурсов лексических анализаторов и анализаторов иллюстрируют использование потоков для связи между ними (или, насколько я понимаю).

Ни один из тех, что я видел, не делает этого.Они полагаются на то, что лексический анализатор является единственным методом, который вызывается синтаксическим анализатором.

...