구문 분석 문법을 수정하여 할당 및 비 할당 문을 허용하는 방법은 무엇입니까?

Question

질문은 아래의 문법에 관한 것입니다. 나는 재미있는 미니 해석 언어로 작업하고있다. (우리는 클래스에서 컴파일러 디자인에 대해 배웠다. 그래서 나는 그것을 다음 단계로 가져 가서 혼자서 시험해보기를 원한다.) 나는 비 터미널 심볼 Expr을 만들려고 노력 중이다.

Expr

Statement ::= Expr SC 
Expr ::=   /* I need help here */ 
Assign ::= Name EQUAL Expr 
AddSub ::= MulDiv {(+|-) AddSub} 
MulDiv ::= Primary {(*|/) MulDiv} 
Primary ::= INT | FLOAT | STR | LP Expr RP | Name 
Name ::= ID {. Name} 

는 Statement이 두 경우를 허용해야 만들 수있다 :

1. x = 789; (세미콜론 뒤에 정규 할당)
2. x+2; (NO 할당 단지 계산 폐기; 이어서 세미콜론)

두 번째 경우의 목적은 m 미래의 광석 변화. 나는 단항 증가 및 감소 연산자와 함수 호출을 생각하고 있었다. 둘 다 의미가있는 과제가 필요하지 않습니다.

나는 다른 문법 (C# 즉)을 보았지만 이해 하기엔 너무 복잡하고 길다. 당연히 솔루션을 찾고있는 것이 아니라 문법을 수정할 수있는 방법에 대한 안내입니다.

모든 도움을 주실 수 있습니다.

EDIT : 내 초기 생각은 Expr ::= Assign | AddSub이라고 말해야하지만 둘 다 비 터미널 기호 Name으로 시작할 수 있으므로 모호성이 생기기 때문에 작동하지 않습니다. 나는 tokenizer가 하나의 토큰을 앞당겨 볼 수있게 만들었지 만 피할 수있는 문제 (애매함)를 고치려고하기 때문에 비 터미널에 대해서는 그런 짓을하지 않았다. 문법에서 터미널은 모두 대문자입니다.

Answer 1

가장 간단한 해결책은 C의 설계자가 다양한 C 파생어에 의해 실제로 취한 해결책입니다. 할당을 단순히 다른 연산자로 처리하고 문장의 최상위 수준으로 제한하지 않습니다. 더 많거나 적은 그 할당을 필요로 특히 구문이 for 성명의 조항에 (

이

while ((ch = getchar()) != EOF) { ... } 

모든 사람이 좋은 스타일을 고려하지만, 그것은 확실히 일반적이다 : 따라서, C에서, 다음은 문제를 일으키지입니다 표정이되어야 함).

가 수행하는 비교적 쉬운 두 개의 작은 합병증은 다음과 같습니다

1. 논리적으로는, 대부분의 사업자는 달리, 오른쪽에 할당 동료 a = b = 0는 a = (b = 0)로 해석되도록하지 (a = b) = 0 (이 될 것입니다 매우 예상치 못한). 그것도 매우 약하게 바인딩, 적어도 오른쪽으로.

   의견은 왼쪽에 얼마나 단단히 묶어야하는지에 따라 다릅니다. C에서는 대부분 엄격한 우선 순위 모델을 따르기 때문에 a = 2 + b = 3은 a = ((2 + b) = 3)으로 구문 분석되므로 거부됩니다. a = 2 + b = 3은 끔찍한 스타일처럼 보일 수도 있지만 a < b ? (x = a) : (y = a)도 고려하십시오. C++에서 삼항 연산자의 결과가 참조가 될 수있는 곳에서는 (a < b ? x : y) = a으로 쓸 수 있습니다. 여기서 괄호는 삼자 연산자보다 우선 순위가 낮다고 생각되는 경우에도 괄호가 필요합니다.

   그러나 이러한 옵션은 문법으로 구현하기 어렵지 않습니다.

2. 많은 언어에서 할당의 왼쪽에는 제한적인 구문이 있습니다. 참조 값을 갖는 C++에서는 제한이 의미 론적이라고 간주 될 수 있으며, 일반적으로 의미 검사로 구현된다고 생각하지만 많은 C 유도체에서 lvalue을 구문 적으로 정의 할 수 있습니다. 이러한 정의는 모호하지 않지만 하향식 문법을 사용하여 구문 분석하기가 쉽지 않으며 상향식 문법의 경우에도 복잡성을 유발할 수 있습니다. 점검 후 분석은 항상 간단한 해결책입니다. 당신은 재귀 하강으로 기술을 분석 하향식를 사용하는 경우

당신이 정말로 표현 문에서 할당 문을 구분하려면

는, 당신은 참으로 예측 실패 ( 하지 모호함)의 문제로 실행합니다. 문법이 모호하지 않기 때문에 간단한 해결책은 bison/yacc와 같은 LALR (1) 파서 생성기를 사용하는 것입니다. bourse/yacc는 어떤 문이 존재하는지 조기에 결정할 필요가 없기 때문에 그러한 문법을 ​​파싱하는 데 문제가 없습니다 파싱 ​​된 전체적으로 LALR (1) 또는 심지어 GLR 파서 생성기를 사용하면 쉽게 읽을 수 있고 구문 분석에 해당하는 형식으로 문법을 지정할 수 있으므로 파서의 구현이 단순 해집니다. 예를 들어, LL (1) 문법은 오른쪽 연관 구문 분석 만 생성 할 수 있기 때문에 LALR (1) 파서는 왼쪽 연관 연산자를 자연스럽게 처리 할 수 ​​있으므로 구문 트리를 일종의 재구성해야합니다.)

A 재귀 하강 파서는 문법이 아닌 컴퓨터 프로그램이며, 그 표현력은 LL (1) 문법의 형식적 제약에 의해 제한되지 않습니다. 그것은 강점과 약점입니다 : 강점은 LL (1) 문법의 한계에 국한되지 않는 해결책을 찾을 수 있다는 것입니다. 약점은 언어의 정확한 구문에 대한 명확한 진술을 추출하는 것이 훨씬 더 복잡하다는 것입니다 (때로는 불가능할 수도 있음). 예를 들어,이 힘은 반복적 인 하강 문법이 위에서 언급 한 제한에도 불구하고 다소 자연스러운 방식으로 왼쪽 연관성을 처리 할 수있게합니다.

이 길을 가고 싶다면 해결책은 간단합니다. 어떤 종류의 함수가 있습니다 :

/* This function parses and returns a single expression */ 
Node expr() { 
    Node left = value(); 
    while (true) { 
    switch (lookahead) { 
     /* handle each possible operator token. I left out 
     * the detail of handling operator precedence since it's 
     * not relevant here 
     */ 
     case OP_PLUS: { 
     accept(lookahead); 
     left = MakeNode(OP_PLUS, left, value()); 
     break; 
     } 
     /* If no operator found, return the current expression */ 
     default: 
     return left; 
    } 
    } 
} 

표현식과 문장을 모두 구문 분석 할 수 있도록 쉽게 수정할 수 있습니다. 먼저 함수를 리펙토링하여 첫 번째 연산자를 사용하여 표현식의 "나머지"를 파싱합니다.

Node expr() { 
    return expr_rest(value()); 
} 

Node stmt() { 
    /* Check lookahead for statements which start with 
    * a keyword. Omitted for simplicity. 
    */ 

    /* either first value in an expr or target of assignment */ 
    Node left = value(); 

    switch (lookahead) { 
    case OP_ASSIGN: 
     accept(lookahead); 
     return MakeAssignment(left, expr()) 
    } 
    /* Handle += and other mutating assignments if desired */ 
    default: { 
     /* Not an assignment, just an expression */ 
     return MakeExpressionStatement(expr_rest(left)); 
    } 
    } 
}