уменьшить / уменьшить конфликты с помощью ocamlyacc - PullRequest
Новая
       35

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

2 голосов
/ 21 марта 2012

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

Все операции, которые работают с разными типами (например, операторы сравнения), вызывают конфликт 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 ]

2 голосов
/ 21 марта 2012

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

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

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

0 голосов
/ 22 марта 2012

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

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

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

...