素語を文字から構成する規則 ... 正規文法(regular grammar)
正規表現 (regular expression)の例
c = getchar(); while (c == ' ') c = getchar(); switch (c) 英字:{ zzleng = 0; do { zztext[zzleng] = c; zzleng++; c = getchar(); } while (cが英字でも数字でもない); backchar(c); zzlex = IDENTIFIER; zzlval = install(zztext,zzleng); } 数字: .... .... '+': zzlex = PLUS; ....
%% ' '+ { REJECT } [a-zA-Z][a-zA-Z0-9]* { yylval = install(yytext,yyleng); return(IDENTIFIER); } [0-9]+ { ... } ... [+] { return(PLUS) } .... %%
文法にもとづく導出による生成ができるかどうかの解析
解析方法
導出での例「式」は最右導出。 最左導出では左再帰的な生成規則がある場合には解析ができなくなる。 この場合、構文規則を書き直して再帰的解析法が使えるように なおす必要がある。
式 => 項 => 項*式 => 係数*式 => 名標*式 => 名標*項 => 名標*係数 => 名標*(式) => 名標*(式+項) => 名標*(項+項) => 名標*(係数+項) => 名標*(名標+項) => 名標*(名標+係数) => 名標*(名標+名標)
のようになる。
「式」の構文規則を変更し、再帰的な解析法を適用したプログラム例を示す。
上の例ではprocedure E(); begin T(); while token = '+' do begin gettoken(); T() end end; procedure T(); begin F(); while token = '*' do begin gettoken(); F() end end; procedure F(); begin if token = '(' then begin gettoken(); E(); if token <> ')' then error(); end else if token = 'i' then gettoken() else error(); end;
のように、構文規則を書き換えている。E -> T, E -> T + T, T -> F, T -> F * F, F -> ( E ), F -> i
L .. 左から素語を調べる
L .. 最左導出
(1) .. 1個の先読み
derive | X->Y1Y2...Yk | 導出 |
error | 誤り |
shift | 読み込み | |
reduce | X->Y1Y2...Yk | 還元 |
accept | 受理 | |
error | 誤り |
repeat s:=スタック最上段の状態; a:=つぎに調べようとしている素語; if A[s,a]=shift then begin t:=G[s,a]; スタックにaとtとをtが最上段に くるように押し込み、入力素語列 からaを取り除く end else if A[s,a]=reduce X->Y1Y2...Yk then begin スタックからk個の状態とk個の 記号を取り出す; u:=スタック最上段の状態; t:=G[u,X]; スタックにXとtとをtが最上段に くるように押し込む end else if A[s,a]=accept then 解析終了 else 誤り forever;
「式」の構文規則としては、
解析表
A | G | |||||||||||||||
状態 | + | * | ( | ) | i | $ | + | * | ( | ) | i | $ | E | T | F | |
0 | s | s | 4 | 5 | 1 | 2 | 3 | |||||||||
1 | s | a | 6 | |||||||||||||
2 | 2 | s | 2 | 2 | 7 | |||||||||||
3 | 4 | 4 | 4 | 4 | ||||||||||||
4 | s | s | 4 | 5 | 8 | 2 | 3 | |||||||||
5 | 6 | 6 | 6 | 6 | ||||||||||||
6 | s | s | 4 | 5 | 9 | 3 | ||||||||||
7 | s | s | 4 | 5 | 10 | |||||||||||
8 | s | s | 6 | 11 | ||||||||||||
9 | 1 | s | 1 | 1 | 7 | |||||||||||
10 | 3 | 3 | 3 | 3 | ||||||||||||
11 | 5 | 5 | 5 | 5 |
解析例
スタック | 素語の列 | 動作 |
---------------- | ---------- | ------ |
$0 | i*(i+i)$ | shift |
$0i5 | *(i+i)$ | reduce 6 |
$0F3 | *(i+i)$ | reduce 4 |
$0T2 | *(i+i)$ | shift |
$0T2*7 | (i+i)$ | shift |
$0T2*7(4 | i+i)$ | shift |
$0T2*7(4i5 | +i)$ | reduce 6 |
$0T2*7(4F3 | +i)$ | reduce 4 |
$0T2*7(4T2 | +i)$ | reduce 2 |
$0T2*7(4E8 | +i)$ | shift |
$0T2*7(4E8+6 | i)$ | shift |
$0T2*7(4E8+6i5 | )$ | reduce 6 |
$0T2*7(4E8+6F3 | )$ | reduce 4 |
$0T2*7(4E8+6T9 | )$ | reduce 1 |
$0T2*7(4E8 | )$ | shift |
$0T2*7(4E8)11 | $ | reduce 5 |
$0T2*7F10 | $ | reduce 3 |
$0T2 | $ | reduce 2 |
$0E1 | $ | accept |
上の構文規則を yacc で書いて、yacc -v コマンドを用いると y.output というファイルができる。