밑에 이어서 , 컴파일러 다시한번만 질문 드립니다...

Sailor_moon의 이미지

안녕하세요 , 컴파일러 기초 클래스 듣고 있는데

난데없이 질문 좀 드립니다 .

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 쪽으로만 트리를 그려도 나올 수 있을것 같은데 ...
처음 그래머 자체를 수정 해야할까요 ?

jick의 이미지

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

Sailor_moon의 이미지

안녕하세요 jick 님 우선 답변 감사드립니다.

주신 링크를 보고 , 한번 다시 작성해 보았습니.

S -> T
T -> 000T | 00T | 엡실론

이렇게 되면 아마도 같은 문법을 생성하는것 같은데요, 이런 식으로 하면 되는것인지요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

jick의 이미지

입력이 00000이라면,

(1) S -> T -> 000 T -> 000 00 T -> 000 00
(2) S -> T -> 00 T -> 00 000 T -> 00 000

두 가지 파스 트리가 가능합니다.
(애매하지 않은 문법이 필요하시다면 좀 더 삽질하셔야 할듯...)

Sailor_moon의 이미지

그렇기는 한데 ... 위와 같은 경우는 left derivation 에 어긋나지 않지 않기 때문에 애매하지 않다고 말할 수 있지 않나요 ?
트리의 모양은 같고 단순히 순서만 다른데요 ....

아니면 지금 이게 하나의 문자만 가지고 대치 되는 형태이기 때문에 어떻게든 애매하게 될 수 밖에 없는것 같은데요 ....

이거 잘 모르겠네요 ㅠ_ㅠ ... 힌트 좀 주실 수 있나요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

snowall의 이미지

문법에서, 하나의 구문에서 둘 이상의 서로 다른 파스트리를 형성할 수 있다면 애매한겁니다.

피할 수 있을때 즐겨라! http://melotopia.net/b

Sailor_moon의 이미지

조언 감사드립니다. 혹시 이런 형태의 애매한 것들을 제거할 수 있는 알고리즘이 있나요 ?

일일히 대입해서 노가다로 저걸 없애보려고 하는데 , 쉽지가 않네요. 알파벳들이 배수의 형태로 생성되기 때문에 반드시 공배수 지점에서는
애매한 게 발생하는데요 .....

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

snowall의 이미지

알고리즘이라기보다는... 가능한 파스트리가 여러개가 있을 때, 파서가 그 중 하나를 적절히 선택하도록 만들면 되겠죠. 아니면, 사람이 의도한 해석과 컴퓨터가 얻은 해석이 다르기 때문이라면, 문법을 더 명확하게 고쳐서 어떤 것이 올바른 것인지 정할 수 있게 해야 할 거고요.

위의 예제에서, 두 경우 중 어느 것이 원하는 건가요?

피할 수 있을때 즐겨라! http://melotopia.net/b

Sailor_moon의 이미지

안녕하세요 snowfall 님 , 후자입니다.
컴퓨터가 해석을 다르게 할 수 있기 때문에 문법을 조금 더 명확히 고쳐 보고자 하는데, 저렇게 배수의 형태는 무조건 모호해 질 거같은데 ... 다른 방법이 있는지요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

Sailor_moon의 이미지

아이쿠 .. 아닙니다 .. 다시 수정했습니다.

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

snowall의 이미지

일단 제 닉네임은 잘못 해석하셨네요ㅎㅎ

피할 수 있을때 즐겨라! http://melotopia.net/b

아기다리의 이미지

'애매하다'의 정확한 정의는 다음과 같습니다.

어떤 룰 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하다고 할 수 있습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.