Я понимаю, как разница между ними, как неоднозначность означает, что есть по крайней мере одна строка с двумя разными деревьями синтаксического анализа, в то время как в однозначном дереве есть только одна. Но я не могу преобразовать одно в другое.
Как преобразовать следующую неоднозначную грамматику в однозначную?
S -> aSb
S -> abS
S -> lambda
Редактировать: хорошо, мой удар по этому поводу будет что-то вроде
S -> aSb | lambda
b -> abS | lambda
Есть предположения?
Грамматика неоднозначна не только потому, что есть два правила, которые соответствуют «а» в качестве следующего токена, но и потому, что «аб» может соответствовать либо первому, либо второму правилу (заменяя S на третье в каждом).
Существует такая вещь, как неоднозначная по своей сути грамматика, но это не так.
Сосредоточившись на этом конкретном примере, я начал с перечисления строк, которые будут анализироваться. Я пронумеровал правила 1, 2 и 3 — и рассмотрел все последовательности, в которых правила 1 и 2 могли появиться в синтаксическом анализе (это два правила, которые генерируют терминалы). N.B. Я предположил, что «лямбда» обозначает пустое производство.
1,2 => ab
11,12 => abab
21,22 => aabb
111,112 => ababab
121,122 => abaabb
211,212 => aababb
221,222 => aaabbb
1111,1112 => abababab
1121,1122 => ababaabb
1211,1212 => abaababb
1221,1222 => abaaabbb
2111,2112 => aabababb
2121,2122 => aabaabbb
2211,2212 => aaababbb
2221,2222 => aaaabbbb
Из этого упражнения очевидно, что мы сопоставляем строки четной длины «a и b», где количество терминалов «a» точно соответствует количеству терминалов «b». Далее, конкатенация двух строк, которые соответствуют приводит к другой совпадающей строке только в том случае, если префикс соответствует второму правилу.
На основе этого анализа я составил несколько новых постановок.
S -> a a X
S -> a b S
S -> lambda
X -> S b b
Эта новая грамматика не является неоднозначной, но соответствует тем же строкам, что и неоднозначная грамматика. Это достигается за счет введения нового нетерминала X. Когда эта CFG используется с автоматами с проталкиванием вниз, дополнительной информации о состоянии, возникающей при использовании как S, так и X, достаточно, чтобы избежать неоднозначности.
Если эта проблема возникла в контексте использования чего-то вроде Yacc или Bison, двусмысленность часто указывает на то, что вы сделали неверный выбор токенов терминала. Если бы вы выбрали «aa», «ab» и «bb» в качестве терминалов, вы не столкнулись бы с трудностями. При использовании (F)lex в качестве токенизатора, как правило, хорошей идеей будет делать совпадающие токены настолько большими, насколько это имеет смысл... поскольку регулярное выражение сопоставляется быстрее (по крайней мере, теоретически), чем контекстно-свободная грамматика - и это, возможно, привело к подходу с двухсимвольным токеном, как само собой разумеющееся.
S->aSb|lambda, B->aBS|lambda, B->b. Вам просто нужно убедиться, что нетерминалы есть только на LHS. То есть, если вы должны придерживаться контекстно-свободной грамматики. - person Ray Toal schedule 19.09.2011