В этом разделе мы сосредоточим внимание на общей генерации с помощью синтаксического анализатора и начнем с простого пошагового руководства по грамматике, похожей на Python, представленной в виде CFG.
Рассмотрим словарь, состоящий из строк типа «d» и «ef», которые можно объединить для создания синтаксиса, подобного Python, в соответствии с неявной CFG, и предположим, что эти строки последовательно выбираются и объединяются в соответствии с процессом, подобным алгоритму 1.
Кроме того, рассмотрим терминальный символ DEF в CFG, который соответствует строке «def» и задается тривиальным регулярным выражением def. Также рассмотрим символ NAME, заданный регулярным выражением [^\W\d]\w* (например, идентификаторы Python). Мы хотим последовательно анализировать строки, выбранные из вышеупомянутого словаря, в соответствии с синтаксисом Python.
Например, одной из таких последовательностей может быть следующая: ["d", "ef", "f", "oo(", "):", " ", "pass"]. Все элементы последовательности по определению являются элементами словаря. Объединение последовательности дает «def foo(): pass», который является допустимой последовательностью токенов, определяющих функцию. В рассматриваемой нами ситуации мы будем наблюдать за всеми токенами до определенного момента и ничего не будем знать о тех, что после этого момента.
Например, в третьем наблюдении в примере последовательности у нас есть объединенная строка «def f». Если бы нам пришлось лексировать/разобрать эту строку, традиционный подход вернул бы последовательность символов DEF NAME, которая ошибочно идентифицирует «f» как полный токен NAME. Как мы видим из остальной части последовательности, правильным токеном NAME будет «foo».
В общем, следующие допустимые строки, которые можно выбрать из словаря, — это те, которые либо
продолжайте расширять/продвигать ИМЯ, начинающееся в данный момент с «f» (как это делает полная последовательность в нашем примере) и/или
все, что начинается с «(» — т. е. символ LPAR с регулярным выражением ( — и далее указывает действительную сигнатуру аргумента.
В первом случае «f» можно рассматривать как частично совпадающий символ ИМЯ в Python, и, вспомнив, что его регулярное выражение — [^\W\d]\w*, мы можем сказать, что он соответствует обоим подшаблонам. (т.е. [^\W\d] и \w*) в регулярном выражении. Наше использование автоматов формализует понятие подшаблонов посредством состояний автомата. В этом случае регулярное выражение для NAME может быть представлено автоматом M с тремя состояниями: 0 (т.е. начальное состояние q0), 1 (т.е. [^\W\d]) и 2 (т.е. \w*). , где 1, 2 ∈ F.
Используя алгоритм 3, мы получили бы последовательности состояний автомата (0, 1), (1, 2), (2, 2) для «f» и автомата M, соответствующего символу NAME. Эти последовательности конечных автоматов для «f» говорят нам, что сопоставление для этой словарной строки может начаться в состояниях 0, 1 или 2 и может закончиться в состояниях 1 или 2.
В соответствии со случаем 1, описанным выше, синтаксический анализ может быть продолжен (для символа NAME) после предыдущего завершения в состояниях 1 или 2. В соответствии со случаем 2, следующая строка также может начинаться с LPAR или содержать его, подразумевая, что M завершился бы. , что возможно, учитывая, что 1 и 2 являются конечными состояниями в M, на которых синтаксический анализ остановился бы после чтения «f». Завершение M также указывает на то, что символ NAME был завершен и что переход в состояние, принимающее LPAR, разрешен грамматикой.
На этом рисунке следующими допустимыми строками словаря являются как минимум "d", "ef", "pass", " ", "oo(", потому что все эти строки будут расширять частично совпадающее ИМЯ, а последняя также будет перевести состояние синтаксического анализа в состояние, позволяющее читать LPAR. Оставшаяся строка «):» из рассмотренного нами подмножества словаря приведет к появлению последовательности с недопустимым синтаксисом.
Применительно к подходу индексирования FSM это означает, что алгоритм 4 будет отображать состояния FSM 0, 1 и 2 в подмножество "d", "ef", "pass", " ", "oo(" для символа NAME и его ФСМ, М.
На этой иллюстрации опущены базовые состояния синтаксического анализатора, которые определяют, какие грамматические символы и переходы разрешены. Мы используем автоматы с понижением уровня (PDA) как средство расширения подхода FSM и решения оставшихся деталей.
4.1. Формулировка автоматов с выталкиванием
Мы определяем автоматы с выталкиванием, используя следующее представление из 6 кортежей [Sipser, 1996, определение 2.13]:
Чтобы построить подход к индексированию для анализатора, управляемого КПК, нам нужно использовать связь между символами CFG – через соответствующий алфавит КПК – и этапами лексического анализа и сканирования, которые создают символы, считываемые КПК.
Более конкретно, синтаксические анализаторы поддерживаются лексерами и сканерами, которые идентифицируют символы из последовательности входных символов, как мы неявно проиллюстрировали в разделе 4. Упорядоченные списки терминальных символов могут быть созданы для каждого состояния синтаксического анализа/PDA на основе разрешенных переходов символов и стека. по отображению δ в каждом состоянии. Это означает, что мы можем построить конечный автомат для каждого состояния синтаксического анализа, который является объединением каждого автомата, соответствующего терминальным символам, считываемым состоянием.
Затем на этапе сканирования будет определен набор возможных терминальных символов V ⊂ Σ для символов, считанных с момента последнего полностью идентифицированного символа в процессе анализа. Например, в начальном состоянии q0 КПК для Pythonlike CFG в разделе 4 сканирование и лексирование строки «de» приведет к V = {DEF, NAME}: т.е. DEF для любой словарной строки, дополняющей строку «def». – за которым следует строка, которая также не читается NAME FSM (например, «def») – и NAME для любых других строк, читаемых его FSM (например, «default»). Обратите внимание, что шаги сканера – и шаги выборки LLM – в конечном итоге уменьшат набор V до тех пор, пока не будет определен единственный терминальный символ v ∈ V.
Применяя алгоритм 3 к каждой строке в V с использованием комбинированных автоматов для каждого состояния синтаксического анализа, мы можем определить конфигурации синтаксического анализатора, состоящие из состояний PDA, соответствующих состояний автомата и потенциальных терминальных символов.
По аналогии с шагами алгоритма 3 мы можем использовать прообраз карты переходов КПК для определения значений стека КПК, который будет читать состояния КПК q ∈ Q и наборы терминальных символов V конфигурации синтаксического анализатора:
Значения стека, предоставляемые этой картой, необходимы для поиска путей (если таковые имеются) через КПК, которые позволяют успешно и полностью анализировать каждую строку в V, начиная с их возможных конфигураций синтаксического анализатора. Для состояний анализатора и комбинаций терминалов, которые соответствуют операциям REDUCE анализатора LALR(1), эти конфигурации анализатора будут состоять не только из значений вершины стека в Γ; они будут состоять из подстеков, соответствующих всем допустимым префиксам для операций REDUCE, связанных со словарной строкой. В конечном счете, каждая конфигурация синтаксического анализатора, которая позволяет выполнить полный анализ словарной строки, добавляется как запись в индекс для КПК, и в этом случае индекс должен быть структурой данных trie, чтобы разрешить запросы к синтаксическому анализатору. значения стека.
Этот документ под лицензией CC 4.0.
L O A D I N G . . . comments & more!
About Author
Writings, Papers and Blogs on Text Models@textmodels
We publish the best academic papers on rule-based techniques, LLMs, & the generation of text that resembles human text.
