Уменьшить / уменьшить конфликты с помощью ocamlyacc

Я борюсь с грамматикой, которая включает в себя типизированные выражения, а также доступ к переменным. Тип результата этого доступа не может быть определен во время синтаксического анализа и оценивается на втором этапе. Эта оценка не является проблемой, но кажется трудно написать однозначные правила синтаксического анализа.

Все операции, которые работают с различными типами (например, операторы сравнения), производят reduce/reduce конфликт. Понятно, что это потому, что парсер не может решить,x.a = y.b"должен быть разобран как"bool_expr EUQAL bool_expr"или как"num_expr EUQAL num_expr"потому что тип является неопределенным. Однако, тип результата comp_op правило определено (так как это всегда логическое значение).

Есть ли решение этой проблемы, не выбрасывая всю информацию о типах во время синтаксического анализа и всегда проверяя ее на этапе оценки?

Вот сокращенный пример грамматики (с использованием ocamllex и ocamlyacc):

comp_op:
  | bool_expr EQUAL bool_expr  { T.Equiv (T.Wrapper $1, T.Wrapper $3) }
  | num_expr EQUAL num_expr    { T.Equiv (T.Wrapper $1, T.Wrapper $3) }
  /* the wrapper type basically just wraps the expressions to get a common type */

bool_expr:
  | TRUE                       { T.Bool true }
  | FALSE                      { T.Bool false }
  | access                     { T.BoolAccess $1 }

num_expr:
  | NUMBER                     { T.Num $1 }
  | access                     { T.NumAccess $1 }

access:
  /* some more complex rules describing the access to variables */

Спасибо за вашу помощь.

Источник

2 ответа

Решение

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

Теоретически, это происходит из-за того, что различия, сделанные с помощью правил ввода, намного тоньше, чем то, что могут выразить традиционные технологии синтаксического анализа. Они пытались задавать правила типизации более декларативно, используя, например, грамматики атрибутов, но ваша обычная технология LL/LR, конечно, не очень подходит, это похоже на разбор вложенных скобок с регулярным выражением.

Наконец, вы должны использовать менгир вместо ocamlyacc, потому что это просто лучше. Вы будете иметь более удобочитаемые и выразительные грамматики (именованные параметры, параметризованные правила...), улучшенные функции отчетов об ошибках и отладки грамматики.

Источник

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

В любом случае, проблема здесь в том, что ваша грамматика не знает тип производства "доступа"; насколько я понял, эта продукция напоминает чтение из переменных, тип которых неизвестен во время анализа. На мой взгляд, вы либо отказываетесь от 100% -ного правильного синтаксического анализа, либо находите способ "волшебным образом" знать тип ваших переменных. Вы можете отслеживать объявления типов и позволить лексеру искать тип переменной, с которой он сталкивается; Затем лексер отправит маркер переменной-идентификатора в зависимости от типа переменной.

Я не уверен, что этот подход работает, потому что я не знаю, как выглядит ваш язык.

Источник
Другие вопросы по тегам