Зубр Shift / Уменьшить конфликт для простой грамматики - PullRequest
Новая
       17

Зубр Shift / Уменьшить конфликт для простой грамматики

2 голосов
/ 30 июля 2010

Я создаю синтаксический анализатор для языка, который я разработал, в котором имена типов начинаются с заглавной буквы, а имена переменных начинаются со строчной буквы, так что лексер может различать и предоставлять разные токены. Кроме того, строка 'this' распознается лексером (это язык ООП) и передается как отдельный токен. Наконец, доступ к членам данных возможен только для объекта this, поэтому я построил грамматику следующим образом: 

%token TYPENAME
%token VARNAME
%token THIS

%%

start:
    Expression
    ;

Expression:
    THIS
    | THIS '.' VARNAME
    | Expression '.' TYPENAME
    ;
%%

Первое правило выражения позволяет пользователю передавать значение this в качестве значения (например, возвращая его из метода или передавая вызов метода). Второе - для доступа к данным об этом. Третье правило - для вызова методов, однако я убрал скобки и параметры, поскольку они не имеют отношения к проблеме. Первоначально грамматика была явно намного больше этой, но это самая маленькая часть, которая генерирует ту же ошибку (конфликт 1 сдвиг / уменьшение) - я выделил ее в свой собственный файл парсера и проверил это, так что ошибка не имеет ничего общего другие символы.

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

Expression '.' VARNAME

конфликта нет. В любом случае, мне, возможно, нужен кто-то, кто излагает очевидное объяснение того, почему возникает этот конфликт и как его разрешить.

Ответы [ 2 ]

4 голосов
/ 30 июля 2010

Проблема в том, что грамматика может смотреть только вперед. Поэтому, когда вы видите THIS, а затем ., вы находитесь в строке 2 (Expression: THIS '.' VARNAME) или в строке 3 (Expression: Expression '.' TYPENAME, через сокращение в соответствии со строкой 1).

Грамматика может уменьшить THIS. до Expression., а затем искать TYPENAME или сдвинуть его до THIS. и искать VARNAME, но она должна решить, когда доберется до . .

3 голосов
/ 31 июля 2010

Я стараюсь избегать y.output, но иногда это помогает. Я посмотрел на файл, который он произвел, и увидел. 

state 1

    2 Expression: THIS.  [$end, '.']
    3           | THIS . '.' VARNAME

    '.'  shift, and go to state 4

    '.'       [reduce using rule 2 (Expression)]
    $default  reduce using rule 2 (Expression)

В основном это говорит, что видит "." и может уменьшить или может сместиться. Уменьшение делает меня иногда anrgu, потому что их трудно штрафовать. Сдвиг является правилом 3 и очевиден (но в выводе не упоминается правило #). Сокращение там, где он видит "." в данном случае это строка 

| Expression '.' TYPENAME

Когда он идет в Expression, он смотрит на следующую букву («.») И входит. Теперь он видит THIS |, поэтому, когда он достигает конца этого оператора, он ожидает «.» когда уйдет или ошибка. Однако это видит "." в то время как между этим и '.' (следовательно, точка в выходном файле), и это МОЖЕТ уменьшить правило, поэтому возникает конфликт пути. Я полагаю, что вы можете использовать %glr-parser, чтобы позволить ему попробовать оба варианта, но чем больше у вас конфликтов, тем больше вероятность, что вы получите неожиданный вывод или ошибку неоднозначности. У меня были ошибки неоднозначности в прошлом. Они раздражают, особенно если вы не помните, какое правило вызвало или повлияло на них. Рекомендуется избегать конфликтов.

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

Я не могу придумать «отличного» решения, но это не дает конфликтов. 

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
    | THIS //trick is moving this AWAY so it doesnt reduce
rval:

    THIS '.' VARNAME

В качестве альтернативы вы можете уменьшить его позже, добавив больше к правилу, чтобы оно не уменьшалось сразу, или добавив токен после или до того, чтобы прояснить, какой путь выбрать или потерпеть неудачу (помните, он должен знать ПЕРЕД сокращением ЛЮБОГО пути ) 

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
rval:
      THIS '@'
    | THIS '.' VARNAME
%%

-edit- примечание, если я хочу сделать func param и type varname, я не могу, потому что тип в соответствии с функцией лексера - это Var (то есть A-Za-z09_), а также тип. param и varname также являются переменными var, так что это вызовет конфликт уменьшить / уменьшить. Вы не можете написать это как они есть, только как они выглядят. Так что имейте это в виду при написании. Вам нужно написать токен, чтобы различать два или записать его как один из двух, но написать дополнительную логику в коде (часть, которая находится в {} справа от правил), чтобы проверить, является ли это funcname или тип и обрабатывать оба этих случая.

...