tiger book読書記録 chapter 3
August 23, 2018
3.1まで読む。文脈自由文法の定義が出てきてた。
August 24, 2018
3.3LR構文解析の途中まで読む。
再帰下降型解析法と文法の書き換えによる曖昧性除去。SLRの定義まで。
途中で簡単な文法で構文解析表が出てくるが実際手を動かしてやって見る必要があるな。3.3を読み終わったらやってみよう。
August 25, 2018
chapter 3本文を読み終える。LR(1) cloure(I)のアルゴリズムが足りない。
I <- I U {(X->.γ)} が抜けている。うーん、明らかな間違いとか翻訳がおかしいとか多すぎるだろう。LL(1), LR(0),LR(1),LALR(1)と一気に解説してある。それも実例に明示しての解説である。状態と構文解析表があっさり提示される。これは読者に自分でもやってみろとことなのだろうなぁ。chapter 3で30pageあまり。実例で十分ということなのだろう。これ以上掘り下げたい人は論文に当たれか。yaccが広く普及しているのだからそれで十分ということか。実際著者はML-lex, ML-yaccを実装して見せてそれを使えと言っているのだしなぁ。
first/follow setの算出を自前でやってみる。次の通り。一体どこを見ているのか分からなくなって何度か初めからやり直した。
grammer 3.20と構文解析表3.22を自前でやってみる。次の通り。答え合わせの為状態番号は同じにした。closureの算出は導出規則を眺めれば自然に出てくるな。gotoの算出も解析位置の(.ピリオド)の位置の変化だからそれに対応する導出規則を見ればいいのか。first, followの算出の方が面倒だな。一体どこを見ているのか分からなくなってやり直す羽目になる。
August 27, 2018
grammer 3.23の状態図と構文解析表(LR(0)とSLR(0)それぞれ)を作成してみた。その際FIRST/FOLLOWを求める必要があったのでそれらも。
Follow(E)={$}となる点がtrickey.ついついFOLLOW(E)がFOLLOW(T)を含むとしてしまい、悩んだ。それ以外では素直にやればよろしい。明日はgrammer 3.26に取り組む予定。状態数が多いので時間がかかるかも。
August 28, 2018
grammer 3.26のLR(0)状態と構文解析表. shift/reduce conflictが起きていることが解る。
grammer 3.26とSLR構文解析表.FIRST set, FOLLOW setも求めている。SLRでもshift-reduce fonflictが解消できないことが解る。これでexercise 3.9の回答にもなっている。
grammer 3.26のLR(1)構文解析表。これでようやくshift-reduce conflictが解消できているのが解る。
LALR(1)状態と解析表の構成はLR(1)の状態をまとめて状態数を減らし解析表を小さくしたものと定義している。LR(1)を経由せずに効率的にLALR(1)状態及び解析表を求めるアルゴリズムについては解説がない。詳しくは参考文献参照ということか。明日以降は残りの文法3.30, 3.35, 3.36をML-yaccにかけてみよう。
August 29, 2018
grammer 3.30, 3.35, 3.36をML-yaccにかけてみる。
%name g3_30などと修正が必要であった。修正無しでは生成された.sig, .smlがsyntax errorになった。うーん、error報告くらいして欲しいなあ。マイナー言語なので仕方がないか。
文法3.35はexpがstart symbolであると警告が出る。progを導入して修正する必要があった。
@@ -1,11 +1,11 @@
%%
%term INT | PLUS | MINUS | TIMES | UMINUS | EOF
-%nonterm exp
+%nonterm prog | exp
%pos int
%verbose
-%start exp
+%start prog
%eop EOF
%name g3_35
@@ -16,6 +16,7 @@
%%
+prog : exp ()
exp : INT ()
| exp PLUS exp ()
| exp MINUS exp ()
文法3.36は%termが間違っていた。
%term ID | ASSIGN | PLUS | MINUS | AND | OR | EQUAL | EOFORが抜けている。予想していたとおり図3.32と図3.37のLR状態はML-yaccで生成したものであった。生成された内容を翻訳するってどうなの？これはそのまま載せてもいいのでは？まぁ、本文中に生成されたものとは書いていないからいいのか。.grm -> .grm.desc, .grm.sig,.grm.smlが生成される。.grm.descに状態が報告される。しかしrule番号が記述無しに使われいてる。.grmに書いたruleの通し番号なのかしら。明日からはプログラミング演習。tiger言語の文法をyaccとして実装することだ。referenceを見ても形式的には定義していないのね。それをやったらほぼ丸コピーで完成してしまうからなぁ。
August 30, 2018
プログラム演習に取り組む。付録にあるtiger言語reference manualに従って書き下す。取り敢えずここまで書いた。まだML-yaccに通してはいないが今日は時間切れである。明日以降はdebugすることになる。
%%
(* yacc declarations *)
%term
EOF
| ID of string | INT of int | STRING of string
| COMMA | COLON | SEMICOLON
| LPAREN | RPAREN | LBRACK | RBRACK | LBRACE | RBRACE
| DOT
| PLUS | MINUS | TIMES | DIVIDE | UMINUS
| EQ | NEQ | LT | LE | GT | GE
| AND | OR
| ASSIGN
| ARRAY | IF | THEN | ELSE | WHILE | FOR | TO | DO | LET | IN | END | OF
| BREAK
| NIL
| FUNCTION | VAR | TYPE
%nonterm program
| exps
| exp
| decs
| dec
| tydec
| vardec
| fundec
| type_id
| ty
| tyfields
| tyfield
| vardec
| funcdec
| lvalue
| eseq
| eseqlist
| negation
| funcall
| arithmetic
| comparsion
| string_comparison
| boolean_exp
| record_creation
| record_fields
| record_field
| array_creation
| assign_stmt
| if_then_else_stmt
| if_then_stmt
| while_stmt
| for_stmt
| let_stmt
%noassoc EQ NEQ LT LE GT GE
%left OR
%left AND
%left PLUS MINUS
%left TIMES DIVIDE
%left UMINUS
%pos int
%verbose
%start program
%eop EOF
%noshift EOF
%name Tiger
(* declarations for error recovery *)
%keyword WHILE FOR TO BREAK LET IN END FUNCTION VAR TYPE ARRAY IF THEN ELSE
DO OF NIL
%prefer THEN ELSE LPAREN
%value ID ("bogus")
%value INT (1)
%value STRING ("")
%%
program : exps ()
exps : exps exp ()
| exp ()
(* declaration *)
decs : decs dec ()
| ()
dec : tydec ()
| vardec ()
| fundec ()
(* type declaration *)
tydec : TYPE type_id EQ ty ()
ty : type_id ()
| LBRACE tyfields RBRACE ()
| ARRAY OF type_id ()
tyfields : tyfields COMMA tyfield ()
| tyfield ()
tyefield : ID COLON type_id ()
(* variable declaration *)
vardec : VAR ID ASSIGN exp ()
| VAR ID COLON type_id ASSIGN exp ()
(* function declaration *)
fundec : FUNCTION ID LPAREN tyfields RPAREN EQ exp ()
(* lvalue *)
lvalue : ID ()
| lvalue DOT ID ()
| lvalue LBRACK exp RBRACK ()
(* expression *)
exp : lvalue ()
| NIL ()
| eseq ()
| INT ()
| STRING ()
| BREAK ()
| LPAREN exp RPAREN ()
| negation ()
| funcall ()
| arithmetic ()
| comparison ()
| string_comparison ()
| boolean_exp ()
| record_creation ()
| array_creation ()
| assign_stmt ()
| if_then_else_stmt ()
| if_then_stmt ()
| while_stmt ()
| for_stmt ()
| let_stmt ()
eseq : LPAREN eseqlist RPAREN ()
eseqlist : eseqlist SEMICOLON exp ()
negation : MINUS exp ()
funcall : ID LPAREN exps RPAREN ()
(* arithmetic expression *)
arithmetic : exp PLUS exp ()
| exp MINUS exp ()
| exp TIMES exp ()
| exp DIVIDE exp ()
| MINUS exp %prec UMINUS ()
(* comparison *)
comparison : exp EQ exp ()
| exp NEQ exp ()
| exp LT exp ()
| exp LE exp ()
| exp GT exp ()
| exp GE exp ()
(* string comparison *)
string_comparison : STRING EQ STRING ()
| STRING NEQ STRING ()
| STRING LT STRING ()
| STRING LE STRING ()
| STRING GT STRING ()
| STRING GE STRING ()
(* boolean expression *)
boolean_exp : exp AND exp ()
| exp OR exp ()
(* record creation *)
record_creation : type_id LBRACE record_fields RBRACE ()
record_fields : record_fields COMMA record_field ()
| record_field ()
record_field : ID EQ exp ()
(* array creation *)
array_creation : type_id OF LBRACK exp RBRACK OF exp ()
(* asssignement *)
assign_stmt : lvalue ASSIGN exp ()
(* flow control statement *)
if_then_else_stmt : IF exp THEN exp ELSE exp ()
if_then_stmt : IF exp THEN exp ()
while_stmt : WHILE exp DO exp ()
for_stmt : FOR ID ASSIGN exp TO exp DO exp ()
let_stmt : LET decs IN exp END ()August 31, 2018
ML-yaccにかけた。まだ、65 shift/reduce conflictsが残っている。算術演算を優先するように文法を変更するのかな。ID()となっていたらlvalueとしてreductionするのではなく関数適用を優先する様に書き換えればいいのだろうか。
September 4, 2018
ML-yaccを通してshift/reduce conflictsを確認した。lvalueとfuncall及びarrayの競合はfuncall, arrayの優先度が高いのでshiftで解決で良いが、precedenceを用いて解決した。if/then/elseのshift/reduce conflictは本文に解説してあるとおりなので、無害。残りのshift/reduce conflictはすべてexp. (reduction)とexp <op> expの(shift)なのでshiftで解決すべきである。よってこれは無害であるとする。付属のtiger.lex.smlはコメントを飛ばしてくれないのね。これは対処しないことにする。修正した.grm fileは次のとおり。あまり納得がいかないが明日からは演習問題。
%%
(* yacc declarations *)
%term
EOF
| ID of string | INT of int | STRING of string
| COMMA | COLON | SEMICOLON
| LPAREN | RPAREN | LBRACK | RBRACK | LBRACE | RBRACE
| DOT
| PLUS | MINUS | TIMES | DIVIDE | UMINUS
| EQ | NEQ | LT | LE | GT | GE
| AND | OR
| ASSIGN
| ARRAY | IF | THEN | ELSE | WHILE | FOR | TO | DO | LET | IN | END | OF
| BREAK
| NIL
| FUNCTION | VAR | TYPE
| LVALUE
%nonterm program
| exps
| exp
| decs
| dec
| tydec
| vardec
| fundec
| ty
| tyfields
| tyfield
| funcdec
| lvalue
| eseq
| eseqlist
| funcall
| args
| arithmetic
| comparison
| boolean_exp
| record_creation
| record_fields
| record_field
| array_creation
| assign_stmt
| if_then_else_stmt
| if_then_stmt
| while_stmt
| for_stmt
| let_stmt
%nonassoc ASSIGN
%left OR
%left AND
%nonassoc EQ NEQ LT LE GT GE
%left PLUS MINUS
%left TIMES DIVIDE
%left UMINUS
%nonassoc LVALUE
%left LBRACK
%left LPAREN
%pos int
%verbose
%start program
%eop EOF
%noshift EOF
%name Tiger
(* declarations for error recovery *)
%keyword WHILE FOR TO BREAK LET IN END FUNCTION VAR TYPE ARRAY IF THEN ELSE
DO OF NIL
%prefer THEN ELSE LPAREN
%value ID ("bogus")
%value INT (1)
%value STRING ("")
%%
program : exps ()
exps : exp ()
| exps exp ()
(* declaration *)
decs : decs dec ()
| ()
dec : tydec ()
| vardec ()
| fundec ()
(* type declaration *)
tydec : TYPE ID EQ ty ()
ty : ID ()
| LBRACE tyfields RBRACE ()
| ARRAY OF ID ()
tyfields : tyfields COMMA tyfield ()
| tyfield ()
tyfield : ID COLON ID ()
(* variable declaration *)
vardec : VAR ID ASSIGN exp ()
| VAR ID COLON ID ASSIGN exp ()
(* function declaration *)
fundec : FUNCTION ID LPAREN tyfields RPAREN EQ exp ()
| FUNCTION ID LPAREN tyfields RPAREN COLON ID EQ exp ()
(* lvalue *)
lvalue : ID %prec LVALUE ()
| lvalue DOT ID ()
| lvalue LBRACK exp RBRACK ()
(* expression *)
exp : lvalue ()
| NIL ()
| INT ()
| STRING ()
| BREAK ()
| if_then_stmt ()
| if_then_else_stmt ()
| while_stmt ()
| for_stmt ()
| let_stmt ()
| eseq ()
| record_creation ()
| array_creation ()
| assign_stmt ()
| funcall ()
| arithmetic ()
| comparison ()
| boolean_exp ()
(* flow control statement *)
if_then_else_stmt : IF exp THEN exp ELSE exp ()
if_then_stmt : IF exp THEN exp ()
while_stmt : WHILE exp DO exp ()
for_stmt : FOR ID ASSIGN exp TO exp DO exp ()
let_stmt : LET decs IN exp END ()
(* expression sequence and paren *)
eseq : LPAREN eseqlist RPAREN ()
eseqlist : eseqlist SEMICOLON exp ()
| exp ()
(* funcall *)
funcall : ID LPAREN args RPAREN ()
args : args COMMA exp ()
| ()
(* arithmetic expression *)
arithmetic : exp PLUS exp ()
| exp MINUS exp ()
| exp TIMES exp ()
| exp DIVIDE exp ()
| MINUS exp %prec UMINUS ()
(* comparison *)
comparison : exp EQ exp ()
| exp NEQ exp ()
| exp LT exp ()
| exp LE exp ()
| exp GT exp ()
| exp GE exp ()
(* boolean expression *)
boolean_exp : exp AND exp ()
| exp OR exp ()
(* record creation *)
record_creation : ID LBRACE record_fields RBRACE ()
record_fields : record_fields COMMA record_field ()
| ()
record_field : ID EQ exp ()
(* array creation *)
array_creation : ID LBRACK exp RBRACK OF exp ()
(* asssignement *)
assign_stmt : lvalue ASSIGN exp ()September 5, 2018
exercise 3.1
exercise 3.1a
((xy*x)|(yx*y))?
s -> term
-> (epsilon)
term -> y xwild y
-> x ywild x
xwild -> x xwild
-> (epsilon)
ywild -> y ywild
-> (epsilon)
exercise 3.1b
((0|1)+"."(0|1)*)|((0|1)*"."(0|1)+)
S -> zerooneplus "." zeroonewild
-> zeroonewild "." zerooneplus
zerooneplus -> zeroorone zerooneplus
-> zeroorone
zeroonewild -> zeroorone zeronewild
-> (epsilone)
zeroorone -> 0
-> 1特に言うことなし。
exercise 3.2
entences:
-> sentence
-> sentences SEMICOLON sentence
sentence:
-> subject-iverb
-> subject-tverb-object
subject-iverb:
-> plural-article-name intransitive-verb like-name
-> single-artcile-name intransitive-verb-s like-name
subject-tverb-object:
-> plural-article-name transitive-verb article-name like-name
-> single-artcile-name transitive-verb-s article-name like-name
like-name:
-> LIKE article-name
-> (epsilon)
article-name:
-> single-article-name
-> plural-article-name
single-article-name:
-> the-or-eps adjective-or-eps TIME
-> an-or-the ARROW
-> a-or-the adjective ARROW
-> a-or-the adjective-or-eps BANANA
-> a-or-the adjective-or-eps FRUIT
plural-article-name:
-> the-or-eps adjective-or-eps FILES
adjective-or-eps:
-> adjective
-> (epsilon)
a-or-the
-> A
-> THE
an-or-the
-> AN
-> THE
the-or-eps
-> THE
-> (epsilon)
adjective: TIME, FRUIT, BANANA
name: TIME, ARROW, BANANA, FILES, FRUIT
single-name: TIME, ARROW, BANANA, FRUIT
plural-name: FLIES
verb: FLIES, LIKE, TIME
intransitive-verb: FRUIT
intransitive-verb-s: FILES
transitive-verb: LIKE, TIME, FRUIT
transitive-verb-s: FILES
article: A, AN, THE
preposition: LIKE
time files like an arrow ; fruit flies like a banana
(time) (files) (like an arrow) ; (fruit) (flies) (like a banana)
(time files) (like) (an arrow) ; (fruit flies) (like) (a banana)うーん、こんなのでいいのかしら。まぁ、問題の趣旨はこういうことなのだろうけれど。
exercise 3.3
ML-yaccのソースコードを載せる。
exercise 3.3a
%%
%term A | B | EOF
%nonterm s | t
%pos int
%verbose
%start s
%eop EOF
%name e3_3a
%%
s: t ()
t: A t A ()
| B t B ()exercise 3.3b
%%
%term A | B | EOF
%nonterm s | t | awild | a_then_b
%pos int
%verbose
%start s
%eop EOF
%name e3_3b
%%
s : t ()
t : awild a_then_b ()
| awild ()
awild : ()
| awild A ()
a_then_b : A B ()
| A a_then_b B ()exercise 3.3c
shift/reduce conflictが一つあるがshiftを受け入れる。
%%
%term LPAREN | RPAREN | LBRACKET | RBRACKET | EOF
%nonterm s | t | balanced_parens_brackets
%pos int
%verbose
%start s
%eop EOF
%name e3_3c
%%
s : t ()
t : ()
| t balanced_parens_brackets ()
balanced_parens_brackets : LPAREN balanced_parens_brackets RPAREN ()
| LBRACKET balanced_parens_brackets RBRACKET ()exercise 3.3d
shift/reduce conflictの解消の為にopen_parensの挿入位置で場合分けを行うことになった。open_parens : ()を含めると上位のruleでの()にconflictが起きてしまう。別解もあるだろうがconflict無しでこれで良しとする。(これ問題文の翻訳が駄目な気がする。)
%%
%term LPAREN | RPAREN | LBRACKET | RBRACKET | EOF
%nonterm s | t | parens_brackets | open_parens
%pos int
%verbose
%start s
%eop EOF
%name e3_3d
%%
s : t EOF ()
t : t parens_brackets ()
parens_brackets : ()
| LPAREN parens_brackets RPAREN ()
| LBRACKET parens_brackets RBRACKET ()
| LBRACKET open_parens parens_brackets RBRACKET ()
| LBRACKET parens_brackets open_parens RBRACKET ()
| LBRACKET open_parens parens_brackets open_parens RBRACKET ()
open_parens : open_parens LPAREN ()exercise 3.3e
これは全ての部分集合の順列を並べるしか思いつかない。実際のcompilerの場合だとすると
keywords -> (epsilon)
-> keywords keyword
keyword -> public
-> final
-> static
-> synchronized
-> transientとして重複を意味解析で検出するのが良い。というのが問題の趣旨なのかなぁ。今日はここまで。
Sep 20, 2018
少し日にちが空いてしまったが再開する．結構忘れているな.
exercise 3.3f
s -> t$
t -> LPAREN statement RPAREN
statement -> statement SEMICOLON statement1
-> statement1
statement1 -> LPAREN statement RPAREN
-> statementこれでいいのかしら，ml-yaccに通して曖昧でない文法を確かめた．;は左結合であることを使って良いなら%left SEMICOLONとして,statement1は必要では無い．
exercise 3.3g
s -> t$
t -> LBRACE exp BRACE
exp -> exp exp1
-> exp1
exp1 -> LBRACE exp RBRACE
-> exp SEMICOLONこれは全問とほぼ同様．semicolonが左結合であることを使って良いならもうちょっと簡単になる．ml-yaccを使用すると生成された.smlにerrorが出る.まぁいいことにする.
exercise 3.4
S -> S1 S2
S2 -> ; S1 S2
S2 ->
S1 -> id := E
S1 -> print ( L )
E -> E1 E2
E2 -> + E1 E2
E2 ->
E1 -> id
E1 -> num
E1 -> ( S, E )
L -> L1 L2
L2 -> , L1 L2
->
L1 -> E左再帰を右再帰に書き換えろという問題か.ヒントには必要なら左括り出しを行なえとあるが一致する生成規則が無いのでこれで終わりなのか.
Sep 21, 2018
exercise 3.5
WORD, begin, endは終端記号であろう.一部WORD, begin, endをW, b, eと略記知ている.
追記FOLLOW(S)に$が含まれていなくて,連鎖的に間違っている.修正する気力も無いので,このままにする.
exercise 3.6
3.6a, 3.6b
exercise 3.6c
B -> Bvが左再帰であるから.実際LL(1)構文解析表で(B, w)に２つの生成規則がある.
exercise 3.6d
S -> u B' D v
B' -> w B
B -> v B
B ->
D -> E F
E -> y
E ->
F -> x
F ->要はB -> Bvの左再帰を右再帰へ書き換えればよいということかな.3.7は*付きで難しいということなので明日.
Sep 26, 2018
exercise 3.7a
次の2生成規則が競合を起こしているので非終端記号Xを導入した.
S -> G$
G -> P X
X ->
X -> G
P -> id : R
R ->
R -> id R3.7b. LL(1)のfirst, followと構文解析表は次の通り.
ここで赤で示した所が競合しているのでLL(1)ではない.しかし,２token先読みして先読み2つ目に終端記号:が含まれていればR->を適用,そうでなければR->idRを適用とすれば競合はなくなるのでLL(2)である.
2.7c
tok: ２つのtokenを返すようにする.
advance: 1tokenを消費して, 1tokenを読み出し,tokの返す値をそれに合わせて変える.こんなのでいいのかなぁ本文中の解説の様に詳しく書くのもダルいか.
2.7d
意味がよくわからない.図3.29を所与のものとして扱って良いなら,自明.(k=2の場合)
LL(k) ならば LR(k)を証明せよという事ならばアルゴリズムを理解していれば自明.(厳密な証明であればまた別なのだろうけど.)
2.7e
正規表現を使うとG=(id : id*)*, P=id : id*, R=id*なので:に注目したら直感的には何も示すことはない気がするのだが,それらしく取り繕ってみる.
受理される記号列の含まれる:の数による帰納法にて示す.
# of : = 0の時,空記号列なので自明
nの時を仮定してn+1に曖昧でない文法であることを示す.ある記号列に対する構文解析木が２つ合った時にそれらが同一であることを示す.
最初にある:に注目し,その記号を含み最下にある非終端記号Pに対応するnodeとその最後の終端記号の位置を考える.すると生成規則よりその位置は次のid :の直前になるので一意に決まる.残りの記号列はn個の:を含むので帰納法の仮定から一意に解析木が決まる.よって解析木が一意に決まるので曖昧な文法でない.これってLL(2)だから曖昧な文法でないとしか言っていないな.
他の証明の仕方としては曖昧な文法であると仮定して,最小数の:を含む曖昧な記号列を考えてするとより短い曖昧な記号列が出来ることを示す背理法か. 曖昧な文法なので記号列と２つ(以上)の構文解析木がある. :が含まれないとすると空記号列になるので一つ以上:が含まれる.最後尾の終端記号:に注目してそれを含むPを考えると２つの構文解析木におけるPは一致するはず.(だってP, Rの構文生成規則がそうなのだから.) なのでその先頭からPの直前に対応する記号列がより少ない:を含む記号列で複数の構文解析木を与える.これは最小の記号列である点に反するので矛盾.
Sep 25, 2018
exercise 3.8
文法を作成するのは省略.LR構文解析ではshiftするから左再帰は自然に扱える.
その分stackを消費する.右再帰は直にreduceするからstackは1構文生成規則分になる.
exercise 3.9上記で既にLR(0)状態と構文解析表は作成済み
exercise 3.10
競合は赤で示した部分.shift/reduce conflict. ML-yaccで答え合わせをしたので,そのソースも載せる.
%%
%term id | COLON | EOF
%nonterm S | G | P | R
%pos int
%verbose
%start S
%eop EOF
%name e3_10
%%
S : G EOF ()
G : P ()
| P G ()
P : id COLON R ()
R : ()
| id R ()
exercise 3.11
SLR文法では無い.LR(0)で下記に示す様にshift/reduce conflictが２つ存在する.state 3でのshift reduceはfollow(P) = {,}なのでSLR文法で解決できる.一方state 8でのshift reduceはfollow(B) = {,}なのでSLR文法では解決できない.
追記FOLLOW(B)に$が含まれていなくて連鎖的に間違っている.結論はSLRである筈.
今日はここまで.後５問ある.なかなか進まない.手でFIRST, FOLLOW, 状態と構文解析表を作るのはダルいが,もう少しだ.手を動かして実感してみないと駄目なところなのだから,頑張ろう.
Sep 26, 2018
exercise 3.12a
exercise 3.12b
LR(0)文法でない.shift/reduce conflictが存在する.
exercise 3.12c
SLR文法である.
exercise 12d.
LR(1)文法である.下記に構文解析表を載せる.
答え合わせのためにML-yaccで検算した.状態数が一致しないので,ML-yaccのmanualに当たる.%verboseで出力されるのはLALRなのね.でも出力される構文解析機はLRであるという.LR 状態だと人間にとって冗長なのかなぁ.ちょっと不思議.
Sep 27, 2018
exercise 2.13
LR状態とSLR構文解析表を下記に示す.shift/reduce conflictがあるのでSLR構文ではない.conflictを起こしている状態を眺めると1token先読みすればconflictを解消できることが見当が付く.
以下にLR(1)状態とLR(1)構文解析表を載せる.状態を眺めると先読みを除いて同じ状態がないことが解る.よってこれはLALR(1)状態とLALR(1)構文解析表でもある.これでこの文法はLALR(1)文法であることが解る.
答え合わせのためのML-yaccのコードは以下.
%%
%term a | b | c | d | EOF
%nonterm S | X | M
%pos int
%verbose
%start S
%eop EOF
%name e3_13
%%
S : X EOF ()
X : M a ()
| b M c ()
| d c ()
| b d a ()
M : d ()exercise 3.14
まず,直感的な説明をする.半端に展開すると,受理される記号列は次の４つ
(E)
E]
(F]
F)
ここで実はE, Fともに空文字列である事に注意すると,最後の記号)か]をみてEかFを判定することは出来ない事が解る.E,Fか判定するためには最左に(があるかどうかの判定が必要.よってLL文法ではあるがLR文法でない.
厳密な証明は状態と構文解析表を作成する.下記にLL(1)構文解析表とLR(1)状態を示す.LL(1)解析表からLL(1)文法であることが解る.一方LR(1)状態からLR(1)文法であることが解る.LALR(1)では緑の状態が同一視される.この時reduce/reduce conflictが起きる.
Sep 28, 2018
exercise 3.15
ML-yaccファイルは次の通り.
%%
%term WHILE | DO | COLON_EQUAL | PLUS | ID | EOF
%nonterm S | E
%pos int
%verbose
%start S
%eop EOF
%name e3_15
%%
S : E EOF ()
E : WHILE E DO E ()
| ID COLON_EQUAL E ()
| E PLUS E ()
| ID ()結果３つのconflictが存在する.それぞれのconflictについて解決方法を述べる.
error: state 8: shift/reduce conflict (shift PLUS, reduce by rule 3)
error: state 9: shift/reduce conflict (shift PLUS, reduce by rule 2)
error: state 11: shift/reduce conflict (shift PLUS, reduce by rule 1)
error: state 8: shift/reduce conflict (shift PLUS, reduce by rule 3)
state 8:
E : E . PLUS E
E : E PLUS E . (reduce by rule 3)
PLUS shift 5
. reduce by rule 3
error: state 9: shift/reduce conflict (shift PLUS, reduce by rule 2)
state 9:
E : ID COLON_EQUAL E . (reduce by rule 2)
E : E . PLUS E
PLUS shift 5
. reduce by rule 2
error: state 11: shift/reduce conflict (shift PLUS, reduce by rule 1)
state 11:
E : WHILE E DO E . (reduce by rule 1)
E : E . PLUS E
PLUS shift 5
. reduce by rule 1state 8: reduceを優先. PLUSは左結合だから
state 9: shift優先 E := (E)と見なすべきだから
state 11: shift優先 while E do (E)と見なすべきだから
次に競合を解決した.grmの載せる.
%%
%term WHILE | DO | COLON_EQUAL | PLUS | ID | EOF | DO_PREC
%nonterm S | E
%pos int
%verbose
%start S
%eop EOF
%right DO
%right COLON_EQUAL
%left PLUS
%name e3_15_a
%%
S : E EOF ()
E : WHILE E DO E ()
| ID COLON_EQUAL E ()
| E PLUS E ()
| ID ()トリッキーなのがDO.DOは演算子ではないが生成規則を眺めるとこれで良いことが解る.
exercise 3.16
もともとの文法.
%%
%term PLUS | MINUS | TIMES | DIV | ID | EOF
%nonterm S | E | B
%pos int
%verbose
%start S
%eop EOF
%name e3_16
%%
S : E EOF ()
E : ID ()
| E B E ()
B : PLUS ()
| MINUS ()
| TIMES ()
| DIV ()優先順位修飾子を用いてconflictを解消したもの
%%
%term PLUS | MINUS | TIMES | DIV | ID | EOF
%nonterm S | E | B
%left PLUS MINUS
%left TIMES DIV
%pos int
%verbose
%start S
%eop EOF
%name e3_16_prec
%%
S : E EOF ()
E : ID ()
| E PLUS E ()
| E MINUS E ()
| E TIMES E ()
| E DIV E ()ここでB-> +|-|*|/展開してEの生成規則にすることが必要.そうでないと%left, %rightを扱うことが出来ない.
文法を書き換えてconflictを解決した物.
%%
%term PLUS | MINUS | TIMES | DIV | ID | EOF
%nonterm S | E | T | F
%pos int
%verbose
%start S
%eop EOF
%name e3_16_grm
%%
S : E EOF ()
E : E PLUS T ()
| E MINUS T ()
| T ()
T : T TIMES F ()
| T DIV F ()
| F ()
F : ID ()exercise 3.17
?X
/ | \
+ ?Y
/ | \
+
?U
/ | \
?V *
/ | \
+?X, ?Yの場合.
?Xの中心記号が+であることから対応する生成記号は
E -> E + T
?X = E
である.
よって?Y = T
Tに対応する生成規則はT -> T * F, T -> T / F, T -> Fの３つであるから
?Y の中心の記号になり得るのは*, /, Fのいずれかで+にはならない
?U, ?Vの場合.
?Uにの真ん中の記号が*であることから対応する生成規則は
T -> T * F
?U = T
である.
よって?V = T
Tに対応する生成規則は T -> T * F, T -> T / F, T -> Fの３つであるから
?Vに対応する中心の記号は*, /, Fのいずれかで+にはならない.
3.15, 3.16, 3.17に*が付いていて難しいことになっているが簡単なのじゃないかなぁ.手でFIRST, FOLLOWを求めて文法状態と文法解析表を作るほうが面倒が気がする.実際上記で間違ってるし.今更直す気力はないですが.やっと３章終了.