내 문법에 포인터를 추가 할 때 충돌 줄이기/줄이기

Question

자기 언어를 만드는 어려움을 더 잘 이해하기 위해 작은 컴파일러에서 작업하고 있습니다. 지금은 문법에 포인터 기능을 추가하는 단계에 있습니다.하지만이를 통해 축소/축소 충돌이 발생합니다.

다음은 bnfc으로 컴파일 할 수있는 간단한 문법입니다. 내가 happy 파서 생성기를 사용하고 그 프로그램은 줄이기/감소 충돌이있다.

entrypoints Stmt ; 

-- Statements 
------------- 
SDecl. Stmt ::= Type Ident; -- ex: "int my_var;" 
SExpr. Stmt ::= Expr;  -- ex: "printInt(123); " 

-- Types 
------------- 
TInt.  Type ::= "int" ; 
TPointer. Type ::= Type "*" ; 
TAlias. Type ::= Ident ; -- This is how I implement typedefs 

-- Expressions 
-------------- 
EMult.  Expr1 ::= Expr1 "*" Expr2 ; 
ELitInt. Expr2 ::= Integer ; 
EVariable. Expr2 ::= Ident ; 

-- and the standard corecions 
_.   Expr ::= Expr1 ; 
_.   Expr1 ::= Expr2 ; 

저는 문법의 학습 단계에 있습니다. 하지만 무슨 일이 일어날 지 알 것 같아.

main(){ 
    int a; 
    int b; 
    a * b; 
} 

및

이

typedef int my_type; 
main(){ 
    my_type * my_type_pointer_variable; 
} 

이 두 프로그램을 고려합니다 (typedef 및 main(){} 부분은 관련 내 문법이 아니다. 그러나 그들은 어떤 상황 줄) 내가하고자하는 첫 번째 프로그램에서

을 a "*" b을 Stmt ==(SExpr)==> Expr ==(EMult)==> Expr * Expr ==(..)==> Ident "*" Ident으로 구문 분석합니다. 즉, 기본적으로 SExpr 규칙을 사용하여 스테핑을 시작합니다.

동시에 규칙을 사용하여 my_type * my_type_pointer_variable을 확장하고 싶습니다. Stmt ==(SDecl)==> Type Ident ==(TPointer)==> Type "*" Ident ==(TAlias)==> Ident "*" Ident.

하지만 문법 단계에서는 원래 식별자가 유형 별칭인지 또는 변수인지 알 수 없습니다.

---

(1) 어떻게 감소/감소 충돌을 제거하고 (2)이 문제가있는 유일한 사람입니까? 확실한 해결책이 있습니까? C 문법이이 문제를 어떻게 해결합니까?

지금까지 "&"또는 "*"대신 다른 기호를 사용하여 성공적으로 내 언어 구문을 변경할 수 있었지만 매우 바람직하지 않습니다. 또한 다양한 공공 문법을 이해할 수없고 왜이 문제가 없는지 알기 위해 노력했지만이 문제에 대해서는 운이 없었습니다.

그리고 마지막으로 어떻게 이러한 문제를 스스로 해결할 수 있습니까? 내가 이해 한 것은 happy에서 더 자세한 출력은 충돌이 일어나는 방법이며, 이러한 충돌을 해결하는 유일한 방법은 영리한 것인가? 나는 예를 들어 도입 할 때 더 많은 문제에 비틀 거릴 까봐 두려워.

Answer 1

이 문제는 일반적으로 "the lexer feedback hack"이라고하는 C 파서에서 다루는 일반적인 방법입니다. 그것은 문법에서 전혀 다루지 않는다는 의미에서의 '해킹'입니다. 대신 렉서가 식별자를 인식 할 때 그 식별자를 typename 또는 non-typename으로 분류하고 각각의 경우에 대해 다른 토큰을 반환합니다 (일반적으로 typename 인 식별자의 경우 'TypeIdent'로, 기타). 렉서는 심볼 테이블의 현재 상태를보고이를 선택합니다. 따라서 구문 분석에서 현재 포인트 이전에 발생한 모든 typedef를 볼 수 있지만 현재 포인트 이후의 typedef는 볼 수 없습니다. 이것이 C가 각 컴파일 단위에서 처음 사용하기 전에 typedef를 선언해야하는 이유입니다.