[질문] C-Style comment를 RE로 어떻게 표현하죠?
글쓴이: 불량도ㅐㅈㅣ / 작성시간: 금, 2005/09/23 - 9:56오후
제가 컴파일러 학교 숙제를 하고 있습니다.
그 중에 하나가 C-style Comment /* */를
NFA => DFA => automatic DFA 로 바꾸는 것입니다.
문제는 Regular Expression을 어떻게 표현하는지 모르겠네요. ㅡㅡ;
제가 아무리 생각해봐도 /*[^*/]**/ 이거라고 생각을 해서
이 RE를 Thompson's construction방식으로 NFA로 만들려고 하니까 안 되더군요.
Thompson's construction 방식에는 a,a|b,ab,a* 이 방식만 책에 설명되어 있습니다.
^(제외시키는) <= 이것을 NFA로 못 만들겠더라구요.
그래서 제가 아무래도 RE를 잘 못 짠 듯한 생각이 들지만, 도저히 생각이 안나요.ㅡㅡ
/* */ 이거 생각보다 RE로 표현하는데 너무 힘들군요. 벌써 3시간째.. 이러고 있음...ㅡㅜ
좀 도와주세요~~
File attachments:
| 첨부 | 파일 크기 |
|---|---|
 C comment automata.png | 18.24 KB |
Forums:
(?xs: / \* .*? \* / )
(?xs: / \* .*? \* / )
[quote]/*.**/[/quote]하면 안되나요? 첫번
하면 안되나요? 첫번째, 세번째 *는 문자 *를 말하는거고, 두번재 *는 0번 이상반복을 의미하는겁니다... ;; 뭐, 실제 구현 문제일테니 뉴라인이나 공백, 탭같은건 그냥 다 . 에 포함된다고 하고 말이지요.
[quote="불량도ㅐㅈㅣ"]그 중에 하나가 C-style Comment
말씀하신 문장만으로는 정확한 스펙을 모르겠습니다만, 일단 다음과 같이 제 마음대로 해석해서 받아들이겠습니다:
어차피 alphabet (the set of symbols)은 유한집합 아닌가요? 즉, 제외시키려는 원소를 제외한 나머지 모든 원소들을 그냥 일일이 a|b 형태로 쫙 묶어주기만 하면 아무 문제가 없을 듯 합니다만……. 일단, alphabet = {a, b, c, /, *}이라고 가정했을 경우의 DFA는 직관적으로도 아래 그림처럼 간단히 만들어집니다. 숙제의 취지에는 맞지 않겠지만, 이런 식의 DFA로부터 역으로 RE를 만들어도 문제가 없을 것 같습니다. :)
PS: 즉흥적으로 슥슥 만들었기에 제대로 확인해보지 않았습니다. 틀렸다면 낭패……. (최소화도 전혀 안되어있을겁니다.) :oops:
[/]--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!
a = * 이고, b = / 일때ba(b*(a*~(a|b)b*)*
a = * 이고, b = / 일때
ba(b*(a*~(a|b)b*)*a*)ab
실제로는 C 주석문은 RE으로 쓰지않고 직관적으로 DFA를 만들 수 있다고 합니다. 그 직관적인 DFA는 밑에 제시한 책에 나와있습니다.
출처 : Compiler Construction, Principles and Practice, Kenneth C. Louden
이렇게 한다면..
"/*"([^*])*"*"+([^*/]([^*])*("*")+)*"/" :)
댓글 달기