시프트/감소 충돌 해결

PLY을 사용하여 this 문법을 구문 분석합니다. 링크 된 스펙에 사용 된 EBNF에 대한 메타그램을 구현했지만 PLY는 여러 개의 시프트/감소 충돌을보고합니다.시프트/감소 충돌 해결

문법 :

Rule 0  S' -> grammar 
Rule 1  grammar -> prod_list 
Rule 2  grammar -> empty 
Rule 3  prod_list -> prod 
Rule 4  prod_list -> prod prod_list 
Rule 5  prod -> id : : = rule_list 
Rule 6  rule_list -> rule 
Rule 7  rule_list -> rule rule_list 
Rule 8  rule -> rule_simple 
Rule 9  rule -> rule_group 
Rule 10 rule -> rule_opt 
Rule 11 rule -> rule_rep0 
Rule 12 rule -> rule_rep1 
Rule 13 rule -> rule_alt 
Rule 14 rule -> rule_except 
Rule 15 rule_simple -> terminal 
Rule 16 rule_simple -> id 
Rule 17 rule_simple -> char_range 
Rule 18 rule_group -> (rule_list) 
Rule 19 rule_opt -> rule_simple ? 
Rule 20 rule_opt -> rule_group ? 
Rule 21 rule_rep0 -> rule_simple * 
Rule 22 rule_rep0 -> rule_group * 
Rule 23 rule_rep1 -> rule_simple + 
Rule 24 rule_rep1 -> rule_group + 
Rule 25 rule_alt -> rule | rule 
Rule 26 rule_except -> rule - rule_simple 
Rule 27 rule_except -> rule - rule_group 
Rule 28 terminal -> SQ string_no_sq SQ 
Rule 29 terminal -> DQ string_no_dq DQ 
Rule 30 string_no_sq -> LETTER string_no_sq 
Rule 31 string_no_sq -> DIGIT string_no_sq 
Rule 32 string_no_sq -> SYMBOL string_no_sq 
Rule 33 string_no_sq -> DQ string_no_sq 
Rule 34 string_no_sq -> + string_no_sq 
Rule 35 string_no_sq -> * string_no_sq 
Rule 36 string_no_sq -> (string_no_sq 
Rule 37 string_no_sq ->) string_no_sq 
Rule 38 string_no_sq -> ? string_no_sq 
Rule 39 string_no_sq -> | string_no_sq 
Rule 40 string_no_sq -> [ string_no_sq 
Rule 41 string_no_sq -> ] string_no_sq 
Rule 42 string_no_sq -> - string_no_sq 
Rule 43 string_no_sq -> : string_no_sq 
Rule 44 string_no_sq -> = string_no_sq 
Rule 45 string_no_sq -> empty 
Rule 46 string_no_dq -> LETTER string_no_dq 
Rule 47 string_no_dq -> DIGIT string_no_dq 
Rule 48 string_no_dq -> SYMBOL string_no_dq 
Rule 49 string_no_dq -> SQ string_no_dq 
Rule 50 string_no_dq -> + string_no_dq 
Rule 51 string_no_dq -> * string_no_dq 
Rule 52 string_no_dq -> (string_no_dq 
Rule 53 string_no_dq ->) string_no_dq 
Rule 54 string_no_dq -> ? string_no_dq 
Rule 55 string_no_dq -> | string_no_dq 
Rule 56 string_no_dq -> [ string_no_dq 
Rule 57 string_no_dq -> ] string_no_dq 
Rule 58 string_no_dq -> - string_no_dq 
Rule 59 string_no_dq -> : string_no_dq 
Rule 60 string_no_dq -> = string_no_dq 
Rule 61 string_no_dq -> empty 
Rule 62 id -> LETTER LETTER id 
Rule 63 id -> LETTER DIGIT id 
Rule 64 id -> LETTER 
Rule 65 id -> DIGIT 
Rule 66 rest_of_id -> LETTER rest_of_id 
Rule 67 rest_of_id -> DIGIT rest_of_id 
Rule 68 rest_of_id -> empty 
Rule 69 char_range -> [ UNI_CH - UNI_CH ] 
Rule 70 empty -> <empty>

충돌 :

id : LETTER LETTER id 
      | LETTER DIGIT id 
      | LETTER 
      | DIGIT

state 4 

    (62) id -> LETTER . LETTER id 
    (63) id -> LETTER . DIGIT id 
    (64) id -> LETTER . 

    ! shift/reduce conflict for LETTER resolved as shift 
    ! shift/reduce conflict for DIGIT resolved as shift 
    LETTER   shift and go to state 10 
    DIGIT   shift and go to state 9 
    |    reduce using rule 64 (id -> LETTER .) 
    -    reduce using rule 64 (id -> LETTER .) 
    (    reduce using rule 64 (id -> LETTER .) 
    SQ    reduce using rule 64 (id -> LETTER .) 
    DQ    reduce using rule 64 (id -> LETTER .) 
    [    reduce using rule 64 (id -> LETTER .) 
    $end   reduce using rule 64 (id -> LETTER .) 
    )    reduce using rule 64 (id -> LETTER .) 
    :    reduce using rule 64 (id -> LETTER .) 
    ?    reduce using rule 64 (id -> LETTER .) 
    *    reduce using rule 64 (id -> LETTER .) 
    +    reduce using rule 64 (id -> LETTER .) 

    ! LETTER   [ reduce using rule 64 (id -> LETTER .) ] 
    ! DIGIT   [ reduce using rule 64 (id -> LETTER .) ]

id 규칙은 프로덕션의 ID가 문자로 시작하도록 보장합니다.

다음 충돌 :

rule_alt  : rule '|' rule

. smiliar 하나

state 113 

    (25) rule_alt -> rule | rule . 
    (25) rule_alt -> rule . | rule 
    (26) rule_except -> rule . - rule_simple 
    (27) rule_except -> rule . - rule_group 

    ! shift/reduce conflict for | resolved as shift 
    ! shift/reduce conflict for - resolved as shift 
    (    reduce using rule 25 (rule_alt -> rule | rule .) 
    SQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    DQ    reduce using rule 25 (rule_alt -> rule | rule .) 
    LETTER   reduce using rule 25 (rule_alt -> rule | rule .) 
    DIGIT   reduce using rule 25 (rule_alt -> rule | rule .) 
    [    reduce using rule 25 (rule_alt -> rule | rule .) 
    )    reduce using rule 25 (rule_alt -> rule | rule .) 
    $end   reduce using rule 25 (rule_alt -> rule | rule .) 
    |    shift and go to state 76 
    -    shift and go to state 74 

    ! |    [ reduce using rule 25 (rule_alt -> rule | rule .) ] 
    ! -    [ reduce using rule 25 (rule_alt -> rule | rule .) ]

연결된 :

rule_except  : rule '-' rule_simple 
       | rule '-' rule_group

나는 이것들을 어떻게 해결합니까?

출처

2017-03-31 Paul Smith

일반적인 스캐너/파서 아키텍처를 사용하는 것에 대해 진지하게 생각해야합니다. 그렇지 않으면 공백을 처리 할 방법을 찾아야합니다.

그렇듯이 공백을 모두 무시하는 것처럼 보입니다. 즉, 파서는 three consecutive identifiers 사이의 공백을 볼 수 없습니다. 그것들은 asoupofundifferentiatedletters으로 함께 실행되는 것을 볼 수 있으며 원래의 의도가 무엇인지 알 수있는 방법이 없습니다. 이것은 문법을 매우 모호하게 만듭니다. 왜냐하면 문법에서 두 식별자가 서로가 차별화된다는 가정하에 서로를 따라갈 수 있기 때문입니다. 모호한 문법은 항상 LR 충돌을 초래합니다.

렉서가 인식하는 식별자 (및 기타 다중 문자 토큰)가 이면 많이입니다. 그렇지 않으면 문법을 다시 작성하여 공백이 허용되는 모든 위치 (예 : (identifer1|identifier2)의 구두점 주변) 또는 필수 항목 (예 : two identifiers)을 식별해야합니다. 또한 다른 문법 문제와 식별자를 제거합니다 정규식을 사용하여 스캐너에서

확인 식별자 :

id -> LETTER LETTER id 
id -> LETTER DIGIT id 
id -> LETTER

는이 규칙이 id을 필요는 숫자 만도에 표시되는 문자의 홀수가 될 수 있습니다 위치. 따라서 a1b은 id이되지만 ab1 또는 ab 또는 a1이 아닐 수 있습니다. 나는 그것이 당신이 의미하는 바가 아니라고 확신합니다.

왼쪽 재귀를 피하려고하는 것 같습니다. 대신 왼쪽 재귀를 받아 들여야합니다. 상향식 파서는 PLY와 마찬가지로 왼쪽 재귀를 좋아합니다. (. 그들은하지만 과도한 파서 스택 사용의 비용으로, 오른쪽 재귀 처리) 그래서 당신이 정말로 원하는 것입니다 :

id: LETTER | id LETTER | id DIGIT

비슷한 변화가 필요한 문법에 다른 장소가 있습니다.

다른 충돌은 조작자 우선 순위의 정교한 처리로 인해 발생하며, 이는 왼쪽 재귀를 피하려는 시도의 결과 일 수 있습니다. EBNF 연산자는 대수 연산자와 마찬가지로 간단한 우선 순위 체계로 파싱 할 수 있습니다. 그러나 우선 순위 선언 (%left 및 친구들)의 사용은 "보이지 않는"연결 연산자 때문에 복잡 할 것입니다. 일반적으로 표준 expr/factor/term 대수 문법에서와 같이 명시적인 우선 순위를 사용하는 것이 더 쉽습니다.

item: id 
    | terminal 
    | '(' rule ')' 
term: item 
    | item '*' 
    | item '+' 
    | item '?' 
seq : term 
    | seq term 
alt : seq 
    | alt '|' seq 
except: term '-' term 
rule: alt 
    | except

- 연산자의 우선 순위에 대한 정보의 부족으로 위의 대응에 except의 처리 : 귀하의 경우, 등가 같은 것을 할 것이다. 이는 명시 적 괄호가없는 연산자 -과 | 연산자를 효과적으로 허용하지 않음으로써 표현됩니다.

# The following will create a problem 
prod: id "::=" rule 
prod_list 
    : prod 
    | prod_list prod

당신은 또한 당신이 변화를 가지고/여기 충돌 감소 발견 할 것이다 (참고 :. 나는 왼쪽 재귀와 함께 문제를 만들지 않습니다 쓴 사실)

그 모호하지는 않지만 하나의 미리보기 토큰으로 왼쪽에서 오른쪽으로 분석 할 수는 없습니다. id이 현재 분석중인 시퀀스의 일부인지 아니면 id 다음에 토큰이 나타날 때까지 새 프로덕션의 시작인지 알 수 없기 때문에 두 개의 토큰이 필요합니다. ::= 인 경우 id은 새로운 생산의 시작과 현재 규칙으로 이동해서는 안됩니다. 그 문제에 대한 일반적인 해결책은 렉서의 해킹입니다 : 렉서는 룩어 헤드의 추가 토큰 하나를 유지하는 함수에 의해 랩 (wrap)되어, id ::=을 definition의 단일 토큰으로 낼 수 있습니다. 다른 SO 질문에는 다양한 LR 파서에 대한 해킹 예제가 많이 있습니다.

그런다고 말하면서 XML을 구문 분석하기 위해 왜 EBNF 용 파서를 구축해야하는지 이해가되지 않습니다. EBNF에서 작업 파서를 작성하는 것은 기본적으로 PLY가 수행하는 것으로 "E"부분을 구현하지 않기 때문에 ?, *, + 및 - 연산자를 사용하는 규칙을 다시 작성해야합니다. - 연산자는 일반적으로 중요하지 않지만이 작업은 자동으로 처리 될 수 있지만 간단하지는 않습니다. 약간 BNF 규칙을 BNF로 다시 작성한 다음 PLY를 사용하는 것이 더 쉬울 것입니다. 그러나 당신이 도전을 찾고 있다면, 그것을 위해 가십시오.

출처

2017-04-03 23:00:57 rici

우선, 당신은 분명히 슬래시로 문법을 번역했습니다. 입력 스트림을 토큰 화해야합니다.

는 일반적으로, ID 같은이 어휘 분석기에 의해 식별되는 단말기보다는 그것은 모든처럼 보이는 문법

id : LETTER LETTER id 
     | LETTER DIGIT id 
     | LETTER 
     | DIGIT

의 일환으로 해석 될 것입니다 당신이 터미널 아래은 안 문법의 일부가되어야한다.

둘째로, 문법에 올바른 재귀를 사용합니다. LALR은 왼쪽과 오른쪽 재귀 모두에서 작동하지만 왼쪽 재귀가있는 작은 테이블을 얻습니다.

는 입력 문자열의 AA

당신이 구문 분석 식별자 주장한다면, 당신이 뭔가 더 마지막으로

id : id LETTER 
    | id DIGIT 
    | LETTER

처럼, Shift 키를 줄 충돌이 반드시 기반으로하지 않는 싶어 있다고 가정합시다. 연산자 표현식에 의해 해결되기 위해 숫자 식에서 자주 발생합니다.

줄이기 - 줄이기 충돌은 항상 잘못됩니다.

출처

2017-04-01 00:58:48 user3344003

이 xml 사양은 문자열을 허용합니다. 'id1 :: = X | "id1 :: = xyz"예를 들면? 우리는 내부 id1이 터미널로 인식되기를 원하지 않습니다. –

어떻게 입력을 토큰화할 것을 제안합니까? 문자열을 토큰 화하는 방법은 무엇입니까? Example id :: = [ "a] | [a"] - 큰 따옴표가 문자열의 일부가 아니라는 것을 어떻게 인식하겠습니까? –

LEX을 사용하십시오. – user3344003

답변

관련 문제