[컴파일러] C Minus 파서 만드는 도중 질문(재귀하강파서)
글쓴이: DevilChoco / 작성시간: 목, 2006/12/14 - 4:00오후
여기에 이런 질문도 괜찮을지 모르겠네요 ^^
컴파일러 파서 제작하는데요
재귀하강 파서로 만들어야 합니다.
책은 Compiler Construction, Principles and Practice, by Kenneth C. Louden 이구요
이 책의 부록에 C- BNF가 나와있습니다. 그래서 그걸 EBNF로 만들었는데
declaration -> var-declaration | fun-declaration
var-declaration -> type specifier ID [ [NUM] ];
fun-declaration -> type specifier ID (params) compound-stmt
(여기서 "ID", "[NUM]", "(", ")"은 터미널 입니다.)
이 부분을 재귀 하강 파서로 구현하는데 declaration이 어디로 가야할지 판단하려면
토큰을 적어도 3개는 봐야 합니다. 이거 어떻게 처리하면 좋을까요??
제 생각에는 좌인수분해(맞나?)해서 문법을 변경시거나,
아니면 그냥 프로그램 상에서 처리해야 하느느 방법밖에 생각이 안나는데...
Forums:
1 개 만 봐도 될것 같은데요?
일단 문법을 단순화 하자면,
( 대문자는 non-terminal, 소문자는 terminal)
D -> V|F
V -> T S id num
F -> T S id (P) C
이렇게 되지요.
종속문법을 상위 문법에 올려 버리면,
D -> T S id num
D -> T S id (P) C
이렇게 되어서, LL(1) 문법이 되지 않습니다.
그래서 left factoring 을 하거나,
LR(1) 혹은 LALR(1), SLR(1) 파싱을 시도 해야 합니다.
left factoring 을 수행 하게 되면,
D -> T S id XX
XX -> num | (P) C
가 되겠네요..(맞나..?)
이러면 LL(1) 문법을 만족하므로 recursive desent parsing 이 가능해 지고요...
LALR(1) 을 사용하신다면 yacc 이라는 툴을 사용하시면 됩니다.
본격적으로 컴파일러를 공부하고 싶으시다면 lex 와 yacc 이라는 툴을 공부해보세요.
파서만들 걱정 없이 구현만 신경쓰면 됩니다. lex 는 lexical analyser 를 알아서 만들어 주고 yacc 는 파서를 알아서 만들어 줍니다.
얇은 사 하이얀 고깔은 고이 접어서 나빌레라
----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라
댓글 달기