Сдвиг / уменьшение конфликта в CUP

Question

Я пытаюсь написать синтаксический анализатор для языка javascript-ish с JFlex и Cup, но у меня есть некоторые проблемы с этими смертельно опасными проблемами сдвига / уменьшения и уменьшения / уменьшения.

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

Моя грамматика следующая: начните с INPUT;

INPUT::= PROGRAM;

PROGRAM::= FUNCTION NEWLINE PROGRAM
| NEWLINE PROGRAM;

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der;

    OPTIONAL ::= 
    | TYPE;


    TYPE::= integer 
    | boolean

    ARG ::=  
    | TYPE id MORE_ARGS;

    MORE_ARGS ::=   
    | colon TYPE id MORE_ARGS;


    NEWLINE ::= salto NEWLINE 
    | ;

    BODY ::=  ;

Я получаю несколько конфликтов, но эти два примера:

 Warning : *** Shift/Reduce conflict found in state #5
 between NEWLINE ::= (*) 
 and     NEWLINE ::= (*) salto NEWLINE 
 under symbol salto
 Resolved in favor of shifting.

 Warning : *** Shift/Reduce conflict found in state #0
 between NEWLINE ::= (*) 
 and     FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
 under symbol function
 Resolved in favor of shifting.

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

Спасибо за ваши ответы.

Answer 1

PROGRAM бесполезен ( в техническом смысле). То есть, он не может дать никакого предложения, потому что в

PROGRAM::= FUNCTION NEWLINE PROGRAM
       |   NEWLINE PROGRAM;

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

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

Дело в том, что ничто - это ничто. Так что, если у вас было много ничего, а кто-то пришел и спросил вас, сколько именно у вас было ничего, у вас возникла бы небольшая проблема, потому что, чтобы получить "много" из "0 * много", вам нужно было бы вычислить "0 / 0", и это не является четко определенным значением. (Если бы у вас было много двоих, и кто-то спросил вас, сколько у вас двоих, это не было бы проблемой: предположим, что из двух получилось 40; вы можете легко вычислить это 40 / 2 = 20, что сработает идеально потому что 20 * 2 = 40.)

Так что здесь у нас нет арифметики, у нас есть строки символов. И, к сожалению, строка, не содержащая символов, действительно невидима, как 0 для всех тех тысячелетий, пока какой-то арабский математик не заметил ценность способности ничего не писать.

Где все это происходит, что у вас есть

PROGRAM::= ... something ...
       |   NEWLINE PROGRAM;

Но NEWLINE разрешено ничего не производить.

NEWLINE ::= salto NEWLINE 
        |   ;

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

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

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

PROGRAM ::= ...
        |   salto PROGRAM;

---

Хотя это не относится к вашей текущей проблеме, я вынужден упомянуть, что CUP - это генератор парсера LALR, и все то, что вы, возможно, узнали или прочитали в Интернете о парсерах рекурсивного спуска, не способных обрабатывать левую рекурсию , неприменимо. (Я удалил напыщенную речь о том, как преподается техника разбора, поэтому вам придется попытаться восстановить ее из оставленных мной подсказок.) Восходящие генераторы синтаксического анализа, такие как CUP и yacc / bison love, оставили рекурсию. Конечно, они могут справиться и с правой рекурсией, но неохотно, потому что им нужно тратить пространство стека на каждую рекурсию, кроме левой рекурсии. Таким образом, нет необходимости искажать вашу грамматику, чтобы справиться с недостатком; просто пишите грамматику естественно и будьте счастливы. (Таким образом, вам редко, если когда-либо нужны нетерминалы, представляющие "остальную часть" чего-либо.)

---

PD: "Ничего особенного" не является культурно-специфической ссылкой на песню из оперы " Порги и Бесс"1934 года.