밑에 이어서 , 컴파일러 다시한번만 질문 드립니다...
글쓴이: Sailor_moon / 작성시간: 토, 2013/02/09 - 6:32오후
안녕하세요 , 컴파일러 기초 클래스 듣고 있는데
난데없이 질문 좀 드립니다 .
Context -free grammar , 우리나라 말로는 문맥 자유 언어 인데요 ..
S -> A | B
A -> 000A | 엡실론
B -> 00B | 엡실론
이걸 정규표현식으로 나타내는 건데 ,
저는 S 는 A 나 B 로 가지 쳐질 수 있고 ,
A 는 다시 000 이 왼쪽에 붙어나가는 형태고 , B 는 00 이 붙어나가는 형태이고 , 이 그래머는 empty 를 만족하니까
그리고 두 왼쪽 , 오른쪽의 가지로 이루어진 언어니까 ..
(000)*U(00)*
이 되겠는건 알겠습니다.헌데 , 이 형태 대로라면 , GRAMMAR 가 ambiguous 하지 않나요 ?
예를 들어 ,
aaaaaa 같이 6의 배수로 나오는 애들은
전부 다
A 쪽으로만 으로도 나올 수 있고, B 쪽으로만 트리를 그려도 나올 수 있을것 같은데 ...
처음 그래머 자체를 수정 해야할까요 ?
Forums:
...
Context-free grammar는 원래 애매할 수 있습니다. (물론 컴파일러를 만들어야 한다면 애매하지 않은 쪽이 좋겠죠.)
더 자세한 내용은 http://en.wikipedia.org/wiki/Ambiguous_grammar
혹은 도서관에서 소위 "베틀북"을 찾아보세요. http://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X/ref=pd_sim_b_2
우선 고맙습니다
안녕하세요 jick 님 우선 답변 감사드립니다.
주신 링크를 보고 , 한번 다시 작성해 보았습니.
S -> T
T -> 000T | 00T | 엡실론
이렇게 되면 아마도 같은 문법을 생성하는것 같은데요, 이런 식으로 하면 되는것인지요 ?
-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!
여전히 애매하죠.
입력이 00000이라면,
(1) S -> T -> 000 T -> 000 00 T -> 000 00
(2) S -> T -> 00 T -> 00 000 T -> 00 000
두 가지 파스 트리가 가능합니다.
(애매하지 않은 문법이 필요하시다면 좀 더 삽질하셔야 할듯...)
jick 님 ...
그렇기는 한데 ... 위와 같은 경우는 left derivation 에 어긋나지 않지 않기 때문에 애매하지 않다고 말할 수 있지 않나요 ?
트리의 모양은 같고 단순히 순서만 다른데요 ....
아니면 지금 이게 하나의 문자만 가지고 대치 되는 형태이기 때문에 어떻게든 애매하게 될 수 밖에 없는것 같은데요 ....
이거 잘 모르겠네요 ㅠ_ㅠ ... 힌트 좀 주실 수 있나요 ?
-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!
문법에서, 하나의 구문에서 둘 이상의 서로 다른
문법에서, 하나의 구문에서 둘 이상의 서로 다른 파스트리를 형성할 수 있다면 애매한겁니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
snowall 님 감사합니다.
조언 감사드립니다. 혹시 이런 형태의 애매한 것들을 제거할 수 있는 알고리즘이 있나요 ?
일일히 대입해서 노가다로 저걸 없애보려고 하는데 , 쉽지가 않네요. 알파벳들이 배수의 형태로 생성되기 때문에 반드시 공배수 지점에서는
애매한 게 발생하는데요 .....
-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!
알고리즘이라기보다는... 가능한 파스트리가 여러개가
알고리즘이라기보다는... 가능한 파스트리가 여러개가 있을 때, 파서가 그 중 하나를 적절히 선택하도록 만들면 되겠죠. 아니면, 사람이 의도한 해석과 컴퓨터가 얻은 해석이 다르기 때문이라면, 문법을 더 명확하게 고쳐서 어떤 것이 올바른 것인지 정할 수 있게 해야 할 거고요.
위의 예제에서, 두 경우 중 어느 것이 원하는 건가요?
피할 수 있을때 즐겨라! http://melotopia.net/b
안녕하세요
안녕하세요 snowfall 님 , 후자입니다.
컴퓨터가 해석을 다르게 할 수 있기 때문에 문법을 조금 더 명확히 고쳐 보고자 하는데, 저렇게 배수의 형태는 무조건 모호해 질 거같은데 ... 다른 방법이 있는지요 ?
-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!
아 ..지금 보니 해석이 하나 더 틀린것 같네요 .
아이쿠 .. 아닙니다 .. 다시 수정했습니다.
-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!
일단 제 닉네임은 잘못 해석하셨네요ㅎㅎ
일단 제 닉네임은 잘못 해석하셨네요ㅎㅎ
피할 수 있을때 즐겨라! http://melotopia.net/b
ambiguity
'애매하다'의 정확한 정의는 다음과 같습니다.
어떤 룰 A -> s가 있을 때, 이 룰을 따랐을 때 나올 수 있는 첫번째 terminal symbol 집합을 FIRST(A -> s)라 하겠습니다.
이 때, A -> s_1, A -> s_2와 같이 두 rule을 잡았을 떄
FIRST(A -> s_1)와 FIRST(A -> s_2)의 교집합이 공집합이 아닌 s_1, s_2가 존재한다면 해당 grammar는 ambiguous합니다.
다음과 같은 grammar에서 :
S -> T
T -> 00T | 000T | epsilon
FIRST(T -> 00T) = {0} , FIRST(T -> 000T) = {0}이므로 해당 grammar는 ambiguous합니다 :)
.
정확히 말하자면 제 본문에서 쓴 '해당 grammar는 애매하다'란 뜻이란 LL parsing 기법을 따를 때 애매하다는 뜻입니다.
혹시 grammar 자체의 ambiguity를 물어보신 것이라면...
grammar 자체의 ambiguity는, 어떤 string을 나타내는 parse tree가 여러개가 나올 수 있을 때 ambiguous하다고 합니다. T -> 00T | 000T | epsilon은 이 의미로도 ambiguous하다고 할 수 있습니다.
댓글 달기