Ответ прост: извлечение лексемы должно производиться в контексте. То, что можно считать лексемами в языке, может значительно различаться в разных частях языка. Например, в COBOL в разделе объявления данных есть строки «PIC» и зависящие от местоположения номера уровней 01-99, которые не отображаются в разделе процедуры.
Таким образом, лексер должен каким-то образом знать, какая часть языка обрабатывается, чтобы знать, какие лексемы собирать. Это часто достигается за счет наличия состояний лексирования, каждое из которых обрабатывает некоторое подмножество всего языкового набора лексем (часто со значительным перекрытием в подмножестве; например, по моему опыту, идентификаторы, как правило, очень похожи). Эти состояния образуют конечный автомат высокого уровня с переходами между ними, когда встречаются лексемы с изменением фазы, например, ключевые слова, указывающие на вход в объявление данных или раздел процедуры программы COBOL. Современные языки, такие как Java и C #, сводят к минимуму потребность в этом, но большинство других языков, с которыми я встречался, действительно нуждаются в такой помощи в лексере.
Так называемые парсеры "без сканирования" (вы думаете "GLR") работают, полностью избавляясь от лексера; теперь лексеру не нужно создавать лексемы, и нет необходимости отслеживать лексические состояния: -} Такие парсеры работают, просто записывая грамматику на уровень отдельных символов; обычно вы найдете грамматические правила, которые являются точным эквивалентом того, что вы бы написали для описания лексемы. Тогда возникает вопрос, почему такой синтаксический анализатор не понимает, какую «лексему» производить? Вот где пригодится часть GLR. Парсеры GLR с удовольствием обрабатывают множество возможных интерпретаций ввода («локально неоднозначный синтаксический анализ») до тех пор, пока выбор в конечном итоге будет разрешен. Итак, что на самом деле происходит в случае «неоднозначных токенов», так это то, что правила грамматики для обоих «токенов» создают нетерминалы для их соответствующих «лексем», и синтаксический анализатор GLR продолжает синтаксический анализ до тех пор, пока один из путей синтаксического анализа не прекратит работу или не завершится синтаксический анализатор. с неоднозначным синтаксическим анализом.
Моя компания создает множество синтаксических анализаторов для языков. Мы используем парсеры GLR, потому что они очень удобны для работы со сложными языками; напишите контекстно-свободную грамматику, и у вас будет синтаксический анализатор. Мы используем экстракторы лексем на основе лексических состояний с обычной спецификацией лексем с помощью регулярных выражений и переходов лексических состояний, запускаемых определенными лексемами. Мы могли бы, возможно, построить безсканирующие анализаторы GLR (заставив наши лексеры выдавать отдельные символы в качестве токенов :), но мы считаем, что эффективность основанных на состоянии лексеров стоит дополнительных хлопот.
В качестве практических расширений наши лексеры на самом деле используют автоматы с расширением стека для конечного автомата высокого уровня, а не просто конечные автоматы. Это помогает, когда у вас есть FSA высокого уровня, подсостояния которого идентичны, и когда лексеру полезно управлять вложенными структурами (например, сопоставить круглые скобки) для управления переключением режима (например, когда все круглые скобки совпадают).
Уникальная особенность наших лексеров: мы также делаем немного того, что делают бессанерные парсеры: иногда, когда ключевое слово распознается, наши лексеры вставляют в анализатор как ключевое слово , так и идентификатор (имитирует безсканирующий парсер с грамматическим правилом для каждого). Разумеется, синтаксический анализатор примет только то, что он хочет «в контексте», и просто отбросит неправильную альтернативу. Это дает нам возможность легко обрабатывать «ключевые слова в контексте, иначе интерпретируемые как идентификаторы», что встречается во многих, многих языках.
person
Ira Baxter
schedule
21.07.2012
