Составители: изменение неоднозначной грамматики

Question

У меня есть небольшая проблема с этим упражнением.

С учетом этой грамматики:

S -> aX | X 
X -> aXb | b | eps 

) показывает, что она неоднозначна со строкой

б) сказать, что язык отражает грамматику

с) изменить грамматику и построить потомка синтаксический анализатор

Решение от меня:

a) Я показывает неоднозначное со строкой «аб»:

- S -> aX -> ab 
- S -> X -> aXb -> ab 

б) грамматика захватывает этот язык:

L = {a^n b^n: n >= 0} U {a^n b^m: n=m+1, n,m >= 0} U {a^n b^m: m=n+1, n,m >= 0} 

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

- G -> X$ 
    X -> aX' | b | eps 
    X' -> XB | eps 

Можете ли вы помочь мне найти правильную грамматику для осуществления или дайте мне вход?

Answer 1

Как you.undoubtedly известно, язык

S -> X | a S b 

может быть описана как «экземпляр X окруженный равным количеством a с и b с». X вот основа рекурсии.

Как вы установили, целевой язык имеет либо равное количество каждой буквы, либо еще одну букву. Поэтому мы можем спросить: «Какое простое определение X могло бы выпустить этот язык?»