다른 제품에서 Bison/Flex, reduce/reduce, 식별자

Question

나는 bison/flex에서 파서를하고 있습니다.

나는 식별자가 모두 boolean_expr 또는 EXPR이 될 수 있도록 할당 생산을 구현하려는

그 유형이 심볼 테이블에 의해 확인됩니다

이 내 코드의 일부입니다.

int a = 1; 
boolean b = true; 
if(b) ... 

그러나, 나는 용어와 boolean_expr 모두의 식별자를 포함하는 경우 감소/감소되고, 모든 솔루션이 문제를 해결하려면 은 그래서 뭔가 같이 할 수 있습니다?

Answer 1

기본적으로 구문에 의미 규칙 (유형 정보)을 주입하는 것입니다. 가능한 일이지만 쉽지 않습니다. 더 중요한 것은, 거의 좋은 생각이 아닙니다. 구문과 의미가 잘 정의되어 있다면 거의 항상 최선입니다.

제시된 모든 문법이 모호하지 않으며 LALR(1)입니다. 그러나 후자의 기능은 취약하기 때문에 문법을 완료하면 어려울 수 있습니다.

예를 들어, 당신은 당신의 질문에 할당 구문을 포함하지 않는,하지만 같이 문법 부분의 나머지 부분과는 달리

assignment: identifier '=' expr 
      | identifier '=' boolean_expr 
      ; 

, 그 생산은 모호하기 때문 :

x = y 

y에 대해 알지 못하는 사이에 y은 term 또는 boolean_expr으로 줄일 수 있습니다.

더 흥미로운 예는 괄호를 문법에 추가하는 것입니다.

term: '(' expr ')' 

boolean_expr: '(' boolean_expr ')' 

결과 문법이 모호 아니지만, 그것은 더 이상 LALR(1)입니다 : 그 일의 확실한 방법은 두 작품을 추가 할 수 없을 것이다. 다음 두 선언을 고려

첫 번째에서

boolean x = (y) < 7 
boolean x = (y) 

이 y 그래서 그 (y)가 term로 감소 할 수있는 int해야합니다; 두 번째 것에서 y은 boolean이어야하며 (y)은 boolean_expr으로 줄일 수 있습니다. 애매 모호하지 않습니다. <이 보이면 (또는하지 않은 경우) 어떤 감소를 선택할 것인지 완전히 분명합니다. 그러나 <는 내다 토큰이 아니며, 사실은 y에서 임의 먼 수 :

boolean x = ((((((((((((((((((((((y... 

그래서 결과 명확한 문법은 k에 대한 LALR(k) 없습니다. 문제를 해결할 수

---

한 가지 방법은 심볼 테이블에 스캐너 액세스를 제공함으로써, 어휘 수준에서 형식 정보를 삽입하는 것입니다.그런 다음 스캐너는 기호 테이블에서 스캔 된 식별자 토큰을보고 심볼 테이블의 정보를 사용하여 세 가지 토큰 유형 중 하나 (더 많은 데이터 유형이있는 경우) 중 하나를 결정할 수 있습니다. undefined_variable, integer_variable 및 boolean_variable. 작동

declaration: "int" undefined_variable '=' expr 
      | "boolean" undefined_variable '=' boolean_expr 
      ; 

term: integer_variable 
    | ... 
    ; 

boolean_expr: boolean_variable 
      | ... 
      ; 

를하지만이는 확장 성이 아니라는 것을 분명해야 : 그럼 당신은 예를 들어,이 것 당신이 유형을 추가 할 때마다, 당신은 문법과 어휘 설명 모두를 확장해야합니다, 이제는 구문이 구문과 섞일뿐 아니라 어휘 분석과 섞여 있기 때문입니다. 의미를 상자에서 빠져 나오게하면 모든 것을 오염시키는 경향이 있습니다.

이 언어가 가장 편리한 솔루션입니다. 예를 들어 typedef 이름과 식별자 이름을 구분하면 C 파싱이 훨씬 쉬우므로 (t)*x이 캐스트인지 곱셈인지 여부를 확인할 수 있습니다. (그러나 더 복잡한 이름 조회 규칙을 갖고있는 C++에서는 올바른 구문 분석을 찾기 위해 의미 분석이 훨씬 필요합니다.)

하지만 솔직히 말해서 당신은 이 아닙니다.은 언어를 디자인하는 방법의 모델로서 C++을 사용합니다. 컴파일러가 분석하기 어려운 언어는 인간이 해석하기가 어렵습니다. , 당신이 어떤없이 AST로 구문 분석 할 수있는 언어와 가장 좋은 선택이야 한마디로

class X { 
    public: 
    X(int n = 0) : data_is_available_(n) {} 
    operator bool() const { return data_is_available_; } 
    // ... 
    private: 
    bool data_is_available_; 
    // ... 
}; 

X my_x_object(); 
// ... 
if (!x) { 
    // This code is unreachable. Can you see why? 
} 

다음 "most vexing parse"은 상대적으로 경험이 풍부한 프로그래머를 여행도 가끔 C++ 이민자를위한 고통의 일반 소스로 계속하고, 의미 론적 정보. 파서가 AST를 생성하면 별도의 패스에서 의미 분석을 수행 할 수 있으며 그 중 하나는 유형 제약 조건을 검사합니다. 그것은 가장 깨끗한 해결책입니다. 명시 적으로 입력 할 필요없이 문법이 약간 expr 지금 어떤 expr 수 있기 때문에, 단순화 :에

expr:  conjunction | expr "or" conjunction ; 
conjunction: comparison | conjunction "and" comparison ; 
comparison: product  | product '<' product ; 
product:  factor  | product '*' factor ; 
factor:  term  | factor '+' term ; 
term:  identifier 
    |  constant 
    |  '(' expr ')' 
    ; 

각 동작 위 단순히 새로운 AST 노드를 생성하고 새 노드로 $$을 설정합니다. 구문 분석이 끝나면 AST를 걸어 모든 expr이 올바른 유형인지 확인합니다.

프로젝트에 잔인한 것처럼 보이는 경우 축소 동작에서 의미 론적 검사를 수행하여 효과적으로 구문 분석과 AST 도보를 혼합 할 수 있습니다. 이는 즉각적인 평가를 위해 편리하게 보일 수 있지만 구문 분석기의 의미 유형에 명시 적 유형 정보를 포함해야하므로 불필요한 오버 헤드가 발생합니다 (언급 한 바와 같이 의미가 파서를 방해하게하는 부적절 함). 다음과 같이 보입니다.

expr : expr '+' expr { CheckArithmeticCompatibility($1, $3); 
         $$ = NewArithmeticNode('+', $1, $3); 
        }