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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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