두 가지에 사용되는 동일한 기호를 처리하는 방법 레몬 파서

Question

도메인 특정 언어를 개발 중입니다. 언어의 일부는 정확성과 기호와 같은 C 표현 구문 분석 구문과 정확히 같습니다.

나는 레몬 파서를 사용하고 있습니다. 나는 두 가지 다른 것들에 사용되는 동일한 토큰의 문제에 부딪쳤다. 나는 렉서의 차이점을 말할 수 없다. 앰퍼샌드 (&) 기호는 '비트 및'및 '주소'모두에 사용됩니다.

처음에는 같은 연관성이 없다는 것을 알기 전까지는 사소한 문제라고 생각했습니다.

어떻게 동일한 토큰에 두 가지 다른 연관성을 부여합니까? 난 그냥 앰퍼샌드()와 같은 AMP를 사용해야하고 주소 및 비트와 규칙을 사용하여 AMP를하거나 다른 토큰 (예 : ADDRESSOF 및 BITWISE_AND) 사용해야합니까. 별도의 기호를 사용하면 렉서 (어쨌든 파서 자체가 아니라는 것을 알 수 없다!)에서 어떤 기호인지 알 수 있어야합니다.

Answer 1

을 명시 적으로, 모든 "우선 순위"레벨에 대해 다른 비 종단을 사용하면 우선 순위를 전혀 선언 할 필요가 없으므로 그렇게해서는 안됩니다.

레몬은 모든 yacc 파생물과 마찬가지로 모호한 문법에서 모호성을 제거하기 위해 선행 선언을 사용합니다. 언급 된 특정 모호한 문법은 다음과 같습니다.

expression: expression '+' expression 
      | expression '*' expression 
      | '&' expression 
      | ... etc, etc. 

이 경우 모든 대안으로 전환 감소 충돌이 발생합니다. 파서 생성기는 우선 순위 규칙을 가지고 있지 않았거나 정확하고 싶었다면, 당신은 (당신이 무슨 짓을했는지입니다) 명확한 문법으로 그 쓰기해야 할 것 :

term: ID | NUMBER | '(' expression ')' ; 
postfix_expr:  term | term '[' expression '] | ... ; 
unary_expr:   postfix_expr | '&' unary_expr | '*' unary_expr | ... ; 
multiplicative_expr: unary_expr | multiplicative_expr '*' postfix_expr | ... ; 
additive_expr:  multiplicative_expr | additive_expr '+' multiplicative_expr | ... ; 
... 
assignment_expr:  conditional_expr | unary_expr '=' assignment_expr | ...; 
expression:   assignment_expr ; 
[1] 

참고 명확한 것을 문법은 심지어 좌 결합 (multiplicative and additive), 위 결합 (right-associative)을 보여줍니다 (할당은 다소 이상하지만, 아래 참조). 그래서 애매 모호하지 않습니다.

자, 우선 순위 선언 (%left, %right 등)을 명확하게하기 위해 사용 만이다. 모호성이 없으면 이 무시됩니다.. 파서 생성기는 문법을 반영하는지 확인하지 않습니다. 사실, 많은 문법을 이런 선행 관계로 표현할 수 없습니다.

결과적으로 문법이 모호하지 않으면 선행 선언을 포함시키는 것이 좋습니다. 그들은 완전히 틀릴 수도 있고 문법을 읽는 사람을 오도 할 수도 있습니다. 언어를 변경해도 문법을 수정하려는 사람을 오도 할 수 있습니다.

우선 순위 규칙과 모호한 문법을 ​​사용하거나 모호하지 않은 문법을 사용하는 것이 더 나은지에 관한 질문이 적어도 있습니다. 문법을 간단한 우선 순위 목록으로 표현할 수없는 C과 같은 언어의 경우 명확한 문법을 ​​사용하는 것이 좋습니다. 그러나 모호하지 않은 문법은 더 많은 상태를 가지며, 파서 생성기가 단위 축소를 ​​최적화 할 수 없다면 위의 문법에서 첫 번째 대안을 모두 사용할 수 없다면 구문 분석을 약간 느리게 할 수 있습니다. AST에 영향을 미치지 않으면 서 표현 형식을 사용해야하며, 대부분은 아무 작업이 아니어도 각 작품을 축소해야하며 많은 파서 생성자가 일부 코드를 삽입합니다.) C은 우선 순위 관계로 간단하게 표현할 수 없습니다 정확하게 대입 연산자입니다. 고려 :

a = 4 + b = c + 4; 

이 때문에 assignment-expression에 구문 분석하지 않습니다, 할당 연산자 만 unary-expression에 왼쪽에 적용 할 수 있습니다. 이는 +과 = 사이의 가능한 숫자 우선 순위를 반영하지 않습니다.

a = ((4 + b) = (c + 4)); 

및 + 낮은 우선이었던 경우

(a = 4) + (b = (c + 4)); 

---

로 구문 분석 : [2]

+가 =보다 높은 우선 순위의라면 발현은 분석 할 [1] 저는 방금 cast_expression을 빠뜨린 것을 알았지 만 다시 넣으려고 할 수는 없습니다. 당신은 아이디어를 얻는다)

[2] 설명이 수정되었습니다.

Answer 2

나중에 디 레퍼런스 (*)와 곱셈 (*) 사이에 동일한 모호성이 있다는 것을 깨달았습니다.

레몬은 기간 뒤에 대괄호 안에 조합 성 선언 (% left/right/nonassoc)에 사용 된 이름을 사용하여 규칙에 대한 유효성을 할당하는 방법을 제공합니다.

나는이 아직 제대로 작동하는지 확인하지 않은,하지만 난 당신이 (끝 부분에 대괄호 가지 유의) 할 수 있다고 생각 : 당신이 규칙을 쓰기 위하여려고하는 경우에

. 
. 
. 

%left COMMA. 
%right QUESTION ASSIGN 
    ADD_ASSIGN SUB_ASSIGN MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN 
    LSH_ASSIGN RSH_ASSIGN AND_ASSIGN XOR_ASSIGN OR_ASSIGN. 
%left LOGICAL_OR. 
%left LOGICAL_AND. 
%left BITWISE_OR. 
%left BITWISE_XOR. 
%left BITWISE_AND. 
%left EQ NE. 
%left LT LE GT GE. 
%left LSHIFT RSHIFT. 
%left PLUS MINUS. 
%left TIMES DIVIDE MOD. 
//%left MEMBER_INDIRECT ->* .* 
%right INCREMENT DECREMENT CALL INDEX DOT INDIRECT ADDRESSOF DEREFERENCE. 

. 
. 
. 

multiplicative_expr ::= cast_expr. 
multiplicative_expr(A) ::= multiplicative_expr(B) STAR cast_expr(C). [TIMES] 
    { A = Node_2_Op(Op_Mul, B, C); } 
. 
. 
. 
unary_expr(A) ::= STAR unary_expr(B). [DEREFERENCE] 
    { A = Node_1_Op(Op_Dereference, B); }