다음 모호한 문법을 ​​어떻게 모호하지 않게 변환합니까?

Question

두 가지의 차이점을 이해합니다. 애매한 트리에 단 하나만있는 반면, 모호성은 2 개의 구별되는 구문 분석 트리가있는 문자열이 하나 이상 있다는 것을 의미합니다. 그러나 나는 하나를 다른 것으로 바꾸는 것처럼 보이지 않는다.

어떻게 다음의 모호한 문법을 ​​모호하지 않은 문법으로 변환합니까?

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

편집 : 좋아,이 나의 찌르기가

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

어떤 생각이 같은 것?

Answer 1

다음 토큰으로 'a'와 일치하는 두 규칙이 있기 때문에 문법이 불명확 할뿐만 아니라 'ab'가 첫 번째 또는 두 번째 규칙 (각각 S에서 세 번째를 사용하여 대체) .

본질적으로 모호한 문법과 같은 것이 있지만, 이것은 하나가 아닙니다.

이 구체적인 예를 집중적으로 살펴보면 구문 분석 할 문자열을 열거하기 시작했습니다. 규칙 1,2와 3에 번호를 매기고 규칙 1과 2가 구문 분석에 나타날 수있는 모든 시퀀스를 고려했습니다 (이 두 규칙은 터미널을 생성하는 두 규칙입니다). 나는 "람다 (lambda)"가 빈 생산을 나타내는 것으로 가정했다. 이 연습에서

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를 사용하는 경우, 토큰을 큰 것으로 일치시키는 것이 좋습니다. 정규 표현식 (적어도 이론적으로는)과 일치하는 것이 더 빠르기 때문에 문맥 자유 문법 (context-free grammar) - 이것은 물론 두 글자 토큰 접근법을 산출 할 수있다.