Заставить лексер рассматривать парсер перед определением токенов?

Я пишу лексер и парсер на ocamllex и ocamlyacc следующим образом. function_name и table_name - это одно и то же регулярное выражение, т.е. строка, содержащая только английский алфавит. Единственный способ определить, является ли строка function_name или table_name, - это проверить ее окружение. Например, если такая строка окружена [ и ], то мы знаем, что это table_name. Вот текущий код:

In lexer.mll,

... ...

let function_name = ['a'-'z' 'A'-'Z']+
let table_name = ['a'-'z' 'A'-'Z']+

rule token = parse
  | function_name as s { FUNCTIONNAME s }
  | table_name as s { TABLENAME s }

... ...

In parser.mly:

... ...

main: 
| LBRACKET TABLENAME RBRACKET { Table $2 }

... ...

Как я писал | function_name as s { FUNCTIONNAME s } перед | table_name as s { TABLENAME s }, приведенный выше код не смог проанализировать [haha]; сначала он рассматривал haha как function_name в лексере, затем он не смог найти для него ни одного соответствующего правила в анализаторе. Если бы он мог рассматривать haha как table_name в лексере, он бы соответствовал [haha] как таблице в анализаторе.

Один из способов решения этой проблемы - точнее использовать лексер. Например, мы определяем let table_name_with_brackets = '[' ['a'-'z' 'A'-'Z']+ ']' и | table_name_with_brackets as s { TABLENAMEWITHBRACKETS s } в лексере. Но я хотел бы знать, есть ли другие варианты. Разве нельзя заставить лексер и синтаксический анализатор работать вместе, чтобы определять токены и сокращение?


parsing lexer ocamllex ocamlyacc menhir
person SoftTimur    schedule 11.08.2020    source источник
comment
Почему function_name и table_name вообще разные типы токенов?   -  person user2357112 supports Monica    schedule 12.08.2020
comment
@ user2357112supportsMonica Я немного упростил. На самом деле регулярное выражение для function_name не совсем то же самое, что и table_name. Они не совсем то же самое, но они перекрывают друг друга.   -  person SoftTimur    schedule 12.08.2020
comment
Измените это примечание в свой вопрос. Это важное уточнение.   -  person rici    schedule 12.08.2020

Ответы (1)


arrow_upward
0
arrow_downward

Вам следует избегать попыток заставить лексер выполнять работу парсера. Лексер должен просто идентифицировать лексемы; он не должен пытаться выяснить, где лексема вписывается в синтаксис. Итак, в вашем (упрощенном) примере должен быть только один лексический тип name. Оттуда парсер разберется.

Но, судя по комментариям, в неупрощенном оригинале два шаблона скорее частично совпадают, чем идентичны. Это раздражает больше, хотя это немного сложнее. По сути, вам нужно выделить общий шаблон как один лексический тип, а затем добавить дополнительные совпадения как один или два других лексических типа (в зависимости от того, является ли один шаблон строгим надмножеством другого).

Это может быть не слишком сложно, в зависимости от точной взаимосвязи между двумя шаблонами. Вы могли бы найти очень простое решение, написав шаблоны в правильном порядке, например, из-за правила самого длинного соответствия:

Если несколько регулярных выражений соответствуют префиксу ввода, применяется правило «самого длинного совпадения»: выбирается регулярное выражение, которое соответствует самому длинному префиксу ввода. В случае ничьей выбирается то регулярное выражение, которое встречается раньше в правиле.

В большинстве случаев это все, что требуется: сначала определить пересечение двух шаблонов как основанную лексему, а затем добавить полные лексические шаблоны каждого контекстного типа для обеспечения дополнительных совпадений. Затем ваш синтаксический анализатор должен будет сопоставить name | function_name в одном контексте и name | table_name в другом контексте. Но это не так уж плохо.

Он потерпит неудачу, когда входной поток не может быть однозначно разделен на лексемы. Например, предположим, что в контексте функции имя может включать символ ?, но в контексте таблицы ? является допустимым оператором postscript. В этом случае вы должны активно препятствовать тому, чтобы foo? анализировался как отдельный токен в контексте таблицы, что означает, что лексер должен знать контекст синтаксического анализатора.

person rici    schedule 12.08.2020