Как вы преобразуете следующую неоднозначную грамматику в однозначную? - PullRequest
Новая
       55

Как вы преобразуете следующую неоднозначную грамматику в однозначную?

0 голосов
/ 19 сентября 2011

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

Как бы я преобразовал следующую неоднозначную грамматику в однозначную? 

S -> aSb
S -> abS
S -> lambda

Редактировать: Хорошо, мой удар в этомбыть чем-то вроде 

S -> aSb | lambda
b -> abS | lambda

есть мысли?

1 Ответ

1 голос
/ 23 сентября 2011

Грамматика неоднозначна не только потому, что есть два правила, которые соответствуют «a» как следующему токену, но и потому, что «ab» может соответствовать либо первому, либо второму правилу (заменяя использование третьего для 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 в качестве токенизатора, как правило, рекомендуется сделать так, чтобы токены, которым он соответствует, были настолько большими, насколько это имеет смысл ... так как быстрее сопоставить регулярное выражение (по крайней мере в теории), чем контекстно-свободная грамматика - и это, конечно, могло привести к использованию двухсимвольного токена.

...