Written by JS970
on April 18, 2023

프로그래밍언어론 2023-04-18 수업정리

Flow

Extended BNF
Syntax Chart
Recursive-Descent Parser

Extended BNF

BNF(Backus-Naur-Form에서 추가로 몇 가지 meta-symbol이 추가된 표기법이다.
$\epsilon, \lambda$ 등 아무 것도 없음을 나타낼 경우 그냥 공백으로 표기한다.

optional Elements

[ ... ]
- <number> ::= <digits>[.<digits>]
- 숫자의 옵션으로 소수점및 소수 부분을 포함할 수 있다는 규칙이다.

Alternative Elements

( ... | ... | ... )
- <signed number> ::= ( + | - ) <number>
- 부호가 있는 정수는 '+' 또는 '-'의 nonterminal을 <number>에 left-associative하게 가진다는 규칙이다.

Sequence of Elements

{ ... } or ${ ... }^*$ or ${ ... }^+$
*, +를 활용한 표기는 non-standard이다.
<identifier> ::= <letter> { <letter> | <digit> }
식별자는 <letter>뒤에 <letter>또는 <digit>이 복수로 위치할 수 있다는 규칙이다.

Syntax Chart

Syntax Diagram, Railroad Diagram이라고도 한다.
syntactic rules를 도식으로 나타낸 것이다.
LHS(EBNF의 좌항)는 시작 화살표의 좌측에 위치한다.
아래 예시는 <expr> ::= { ('+' | '-') } 을 Syntax Chart로 나타낸 것이다.

Pascal if-then-else Railroad Diagram

Pascal Railroad Diagram

위의 Railroad Diagram으로부터 역으로 EBNF를 뽑아낼 수 있다.

<if else then> := 'if' <boolean expression> 'then' <compound> 
					( <else if> | <else> ) 'end'

Recursive-Descent Parser

parser란 string을 tree(generalized list)로 바꾸는 프로그램이다.
- 주어진 문법에 대해서 parser는 syntax를 check한다.
Parser Generator
- YACC(Bison)
- AntLR
- CUP
Parser를 직접 만들수도 있다.

Recursive-Descent Parser

순환 하강 구문분석기
parse tree의 위쪽 노드에서부터 하강하면서 이동하여 검사한다.
한 노드에서 재귀적으로 이동하여 검사할 수도 있다.

Transform Grammar to Recursive-Descent Parser

문법은 left-factored해야 하며, EBNF를 사용하여 left-recursion을 제거해야 한다.
모든 논터미널 기호에 대해 right-hand side의 production rule을 simulation하는 subprogram을 생성해야 한다.
토큰 등 터미널 기호에 대해서는 match(eat up)를 통해 symbol처리를 한다.
Global variable LA(lookahead)를 사용하여 현재 토큰을 저장한다.
- 추가적인 속성 문법을 위한 변수를 선언해야 할 수도 있다.
yylex()
- 다음 토큰을 반환한다.
match(int t)
- (인자로 받은 토큰에 대해) 검사 후 전진
- 현재 토큰에 대해 처리한다.
- 문법에 부합하면 전진
아래는 matching parentheses에 대한 grammar를 검사하는 parser이다.
- 우선 문법을 정의한다.
```
A := eof | L A
L := S 'newline'
S := (S)S | ;
```
- 이를 바탕으로 위에서 설명한 규칙에 맞게 C언어로 parser를 작성하면 아래와 같다.

#include <stdio.h>
 
int LA;
int yylex() {
    return getchar();
}
 
void match(int t) {
    if(LA == t) LA = yylex();
    else fprintf(stderr, "Syntax Error\n");
}
 
int S() {
    if(LA == '(') {
        match('(');
        S();
        match(')');
        S();
    }
    else
    ;
}
 
int L() {
    S(); match('\n');
}
 
int A() {
    if(LA == EOF)
    ;
    else {
        L(); A();
    }
}
 
int main() {
    LA = yylex();
    A();
    return 0;
}

실행 결과

Top