Неоднозначная грамматика (с использованием зубров) - PullRequest
Новая
       41

Неоднозначная грамматика (с использованием зубров)

0 голосов
/ 11 августа 2011

У меня проблема с неоднозначной грамматикой. Я получил это: 

%token identifier
%token lolcakes

%start program

%%

program
    : call_or_definitions;

expression
    : identifier
    | lolcakes;

expressions
    : expression
    | expressions ',' expression;

call_or_definition
    : function_call
    | function_definition;

call_or_definitions
    : call_or_definition
    | call_or_definitions call_or_definition;

function_argument_core
    : identifier
    | identifier '=' expression
    | identifier '=' '{' expressions '}';

function_call
    : expression '(' function_arguments ')' ';';

function_definition
    : identifier '(' function_definition_arguments ')' '{' '}';

function_argument
    : lolcakes
    | function_argument_core;

function_arguments
    : function_argument 
    | function_arguments ',' function_argument

function_definition_argument
    : expression function_argument_core
    | function_argument_core;

function_definition_arguments
    : function_definition_argument
    | function_definition_arguments ',' function_definition_argument;

Это подмножество моей подлинной грамматики, которую можно компилировать отдельно. В данный момент он генерирует конфликт S / R между function_call и function_definition при обнаружении потока identifier (. Я пытаюсь убедить Бизона в том, что ему не нужно принимать решение позднее в потоке токенов, объединяя грамматику для вызовов функций и определений функций. Другими словами, если он сталкивается с чем-то, что является общим для вызовов и определений, он может уменьшить это без необходимости знать, что есть что, и если он встретит что-то еще, то что-то еще будет четко обозначать, что есть что. Это вообще возможно, и если да, то как я могу это сделать? Я действительно предпочел бы избежать изменения структуры входного потока, если это возможно.

Ответы [ 2 ]

1 голос
/ 11 августа 2011

Проблема в том, что expression может состоять из одного identifier.В это время парсер должен решить, будет ли он только identifier или уменьшит его до expression, поскольку это определит путь позже.

1 голос
/ 11 августа 2011

Проблема не должна возникать, пока вы не увидите identifier ( identifier с прогнозом , или ).В этот момент парсер должен решить, уменьшать ли второй идентификатор как function_definition_argument или expression (чтобы стать function_argument).

Вы можете решите это чисто в грамматике грубой силой, но это приведет вас в лабиринт нетерминалов, таких как expression_not_naked_identifier и ambiguous_begining_of_function_defn_or_call, с результирующим безудержным дублированием семантических действий.

Вероятно, было бы большесопровождаемые (и приводящие к более понятным сообщениям об ошибках синтаксиса), чтобы написать что-то вроде 

definition_or_call_start: identifier '(' generic_argument_list ')'
generic_argument_list: generic_argument
                     | generic_argument_list ',' generic_argument
generic_argument: expression 
                | function_argument_core
                | ...
function_call: definition_or_call_start ';';
function_definition : definition_or_call_start '{' '}';

и затем проверить как семантическое ограничение в действии для двух последних производств, что фактический generic_arguments, который вы проанализировали, соответствуетиспользовать их.

...