как порядок в этом рекурсивном правиле не дает того же результата? - PullRequest
Новая
       36

как порядок в этом рекурсивном правиле не дает того же результата?

0 голосов
/ 07 января 2019

Может кто-нибудь сказать мне, в чем разница между следующими двумя правилами (обратите внимание на порядок)?

  1. первый, который не работает 

    without => "[" "]"  without | "[" "]"
with => "[" INDEX "]"  with | "[" INDEX "]"
array => ID with | ID without | ID with without

  2. вторая, которая вроде бы работает 

    without => without  "[" "]"| "[" "]"
with => with "[" INDEX "]"  | "[" INDEX "]"
array => ID with | ID without | ID with without

Я пытаюсь добиться синтаксиса массива n-dims с размером, подобным массивам C #. Таким образом, следующий синтаксис должен работать arr[], arr[1], arr[1][], arr[1][1], arr[][], но не такой, как arr[][1].

1 Ответ

0 голосов
/ 07 января 2019

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

Вопрос прост. Помните, что анализатор снизу вверх LALR (1), подобный генерируемому bison, выполняет каждое сокращение точно в конце правой части, принимая во внимание только следующий токен («токен предпросмотра»). Таким образом, он должен знать, какую продукцию использовать в данный момент, продукция полностью прочитана. (Это дает ему гораздо больше широты, чем анализатор, работающий сверху вниз, который должен знать, какую продукцию он будет использовать в начале производства. Но этого все же не всегда достаточно.)

Проблемным случаем является производство ID with without. Здесь любой входной сигнал, соответствующий with, должен быть уменьшен до одного нетерминала with, прежде чем продолжить с without. Чтобы добраться до этой точки, анализатор должен был пройти через некоторое количество '[' INDEX ']' измерений, а токен предварительного просмотра должен быть [, независимо от того, имеет ли следующее измерение определенный размер или нет.

Если правило with является праворекурсивным: 

with: '[' INDEX ']' with
    | '[' INDEX ']'

тогда парсер действительно застрял. Если то, что следует, имеет определенное измерение, оно должно продолжать пробовать первое производство, что означает сдвиг [. Если то, что следует, не имеет INDEX, ему нужно уменьшить второе производство, что вызовет цепочку сокращений, ведущую к началу списка измерений.

С другой стороны, с левым рекурсивным правилом: 

with: with '[' INDEX ']'
    | '[' INDEX ']'

У парсера вообще нет проблем, потому что каждый with уменьшается, как только замечен ]. Это означает, что синтаксический анализатор не должен знать, что следует, чтобы принять решение об уменьшении. Он выбирает между двумя правилами, основанными на прошлом, а не на будущем: первое измерение в array использует второе производство, а остальные (которые следуют за with) используют первое.

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

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

array  : ID dims
dims   : without
       | '[' INDEX ']'
       | '[' INDEX ']' dims
without: '[' ']'
       | '[' ']' without

Здесь грамматика принимает только пустые измерения в конце списка из-за структуры dims. Но для достижения этого эффекта dims должен быть праворекурсивным, поскольку это конец списка с расширенным синтаксисом.

...