C- 문법을 LL (1)로 변환

Question

현재 C- 용 컴파일러를 작성 중입니다. 나는 현재 파서를 만들고 있는데, 어떤 이유로, (단말 ID의) 초기 설정 충돌을 EXPRESSION 생산에서 해결할 수 없다. 아래에, 내가 가지고있는 문법의 하위 집합인가, 누군가가 충돌을 해결하는 방법 (또는 동등한 LL (1) 구문 분석 가능한 문법으로 변환하는 방법)에 관해 올바른 방향으로 나를 가리킬 수 있습니까?

EXPRESSION -> id VAR eq EXPRESSION | SIMPLEEXPRESSION 

VAR -> lbracket EXPRESSION rbracket | empty 

SIMPLEEXPRESSION -> ADDITIVEEXPRESSION FADDITIVEEXPRESSION 

FADDITIVEEXPRESSION -> RELOP ADDITIVEEXPRESSION | empty 

RELOP -> ltoreq | lt | gt | gtoreq | doubleeq | noteq 

ADDITIVEEXPRESSION -> TERM ADDITIVEEXPRESSION1 

ADDITIVEEXPRESSION1 -> ADDOP TERM ADDITIVEEXPRESSION1 | empty 

ADDOP -> plus | minus 

TERM -> FACTOR TERM1 

TERM1 -> MULOP FACTOR TERM1 | empty 

MULOP -> times | divide 

FACTOR -> lparen EXPRESSION rparen | id FACTOR1 | num 

FACTOR1 -> a | b 

Answer 1

C는 LL에 잘 적합하지 않습니다 (1) 파싱, 그래서 당신은 달성하기 매우 어려울 수 여기서 뭘하려고, 심지어 전체 문법 가능하지 않을 수 있습니다 무엇.

그러나 최상위 생산을위한 손의 문제에 대한

EXPRESSION -> id VAR eq EXPRESSION | SIMPLEEXPRESSION 

는 id는 그래서 LL (1) 파서는 알 수 없습니다, 두 대안의 시작이 될 수 있다는 것을 쉽게 알 수있는 대안 선택하기. id 대안을

EXPRESSION  -> EXPRESSION_id | EXPRESSION_non_id 

, 우리는 것 : 즉각적인 문제에

하나의 해결책은하지 않을 두 가지 대안, 항상 id 터미널로 시작 하나, 하나에 EXPRESSION 생산을 분할하는 것 최대 정면 id 단자를 필요로하고 따르는 프로덕션 id 오닐 버전 생성 : t 들어

EXPRESSION_id  -> id (VAR eq EXPRESSION | SIMPLEEXPRESSION_id) 

을 마찬가지로

EXPRESSION_non_id -> SIMPLEEXPRESSION_non_id 

필요한 하위 제작이 같은 보일 것이다 문법을 완료 :

SIMPLEEXPRESSION_id -> ADDITIVEEXPRESSION_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_id -> TERM_id ADDITIVEEXPRESSION1 
TERM_id -> FACTOR_id TERM1 
FACTOR_id -> FACTOR1 

SIMPLEEXPRESSION_non_id -> ADDITIVEEXPRESSION_non_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_non_id -> TERM_non_id ADDITIVEEXPRESSION1 
TERM_non_id -> FACTOR_non_id TERM1 
FACTOR_non_id -> lparen EXPRESSION rparen | num 

당신은 수를 그는 id면, 우리는 따르는 생산의 비 id 버전을 만들 것입니다 비 다른 충돌에 대해서도 유사한 변환을하지만 결과 문법은 매우 다루기 힘들어 질 수 있습니다.