Microsoft PowerPoint - 13Kadai.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 13Kadai.pptx"

ありあさくもと
4 years ago
Views:

1 提出講義での説明を聞いて下さい櫻井彰人コンパイラ理論課題締め切りは 8 月 1 日とします順不同でできるものをできるだけ多く回答して下さい電子メールで sakurai あっと ae どっと keio どっと ac どっと jp に送ってくださいファイル形式は pdf か MsWord でただしプログラムはテキストファイルでレポート課題 1 それぞれ 1 問として考えます電卓タイプのプログラムで浮動小数点数を実装して下さい字句解析部分だけの改造ですみます電卓タイプのプログラムで大小等不等を判別する式と論理式を実装してください電卓タイプのプログラムで代入式を実装して下さい補足論理式論理式の導入は直線的優先順位に注意算術演算子より弱いただ論理式は限られた場所だけで用いることにする rule target: exp lexp lexp: exp '==' exp result = (val[0]==val[2]) exp '!=' exp result = (val[0]!=val[2]) exp '>=' exp result = (val[0]>=val[2]) exp '<=' exp result = (val[0]<=val[2]) exp '> exp result = (val[0]> val[2]) exp '<' exp result = (val[0]< val[2]) lexp '&&' lexp result = (val[0] && val[2]) lexp ' ' lexp result = (val[0] val[2]) '!' lexp result =!( val[1]) '(' lexp ')' result = val[1] TRUE result=true FALSE result=false 忘れてはいけない nonassoc '==' '!=' '>=' '<=' '>' '<' nonassoc '!' left '&&' ' ' when / A(== >= <=!=)/ when / A(&& )/ 勿論まとめても結構最も弱いところに追加エスケープ記号の右なので文字としての縦棒

2 少々無理ですが print ぐらいしたいので args : result = [] exp result = val # result = [val[0]] lexp result = val args ',' exp result.push( val[2] ) ヒント : 代入式下記のようなものがどこかに書かれています IDENT '=' exp result = do_assign( val[0], val[2] ) def do_assign( vname, val vname ] = val レポート課題 2 練習問題 3: 直前結果の参照変数と関数呼び出しが使えるようにして下さい直前の結果を参照することができると便利です %% という特別な変数を用意してくださいそして? Math.exp(3) = ? x=%%*2 = ヒント : 直前結果の参照 when / A%%/ と '%%' result = do_parse をしかるべきところに入れればよい. (3 番目は入れるではなく置き換えるです )? レポート課題 3 calc.y で文字列を扱えるようにして下さい intp.y の文字列部分をコピーすればよいスキャナーの "NUMBER" のあとに when / A"(?:[^" ]+.)*"/, / A'(?:[^' [:STRING, eval($&) ] exp の定義中 ( "NUMBER" のあとに ) STRING 上記の正規表現は何を行っているのか説明して下さいレポート課題 4 ファイルが読めるようにしよう行番号も実装しよう ---- footer コマンドライン引数の 1 番目 parser = Calcp.new begin if ARGV.length>=1 then デフォールトのファイル名 fname = ARGV[0] else fname = 'test' 行番号関連 File.open(fname) f parser.parse(f) rescue NoMethodError, ArgumentError, ParseError print $!, " at line #parser.lineno", " n" ファイルを一行ずつ処理します def parse(str) lineno = 1

3 ファイルが読めるようにしよう (2) def = 1 f.each do line line.strip! print( ">>", line, " n" ) until line.empty? case line line = [false, '$'] do_parse puts( "=>"+@result.to_s += 1 target: = result /* none = result = 0 def 下記も可 attr_reader :lineno += [false, = do_parse def = 0 f.each do line %% 用です def rescue NoMethodError, ArgumentError, ParseError print $!, " at line #parser.lineno", " n" レポート課題 5 練習問題 4: if then else Ruby の if then else と if then 相当の文が使えるようにしてください if 部分には数式を書きその値が 0 ならば else 部分の値を 0 以外であれば then 部分の値を if 式の値とする何となくできるようにするのは簡単です例えば then 部分 else 部分には " 代入のない " 式しか現れないとする無駄な計算をしてもよいとする結果には不要な式 ( 例えば条件が成立しているときの else 部分 ) の計算をしてもよいとする例解例えば exp の定義に次のようなものを付け加えればよい if val[1]!=0 then result=val[3] else result=nil if val[1]!=0 then result=val[3] else result=val[5] a = 0 if a then 1 else 2 = 2 a = 1 if a then 1 else 2 = 1 プログラム作成上の注意 if, then, else, といったキーワードが出てくる変数として認識しては困る予約語 ( つまりシステムが使用することを予約している語 ) とする def parse(str) when / A[a-zA-Z_] w*/ word = [(RESERVED[word] :IDENT), RESERVED_V.key?(word)? RESERVED_V[word] : word.intern ] when / A d+. [:NUMBER, $&.to_f] RESERVED = 'if' => :IF, 'else' => :ELSE, 'while' => :WHILE, 'then' => :THEN, 'do' => :DO, 'def' => :DEF, 'true' => :TRUE, 'false' => :FALSE, 'nil' => :NIL, '' => :END RESERVED_V = 'true' => true, 'false' => false, 'nil' => nil しかし失敗? 代入式が書けるようにすると結果が思わしくない if val[1]!=0 then result=val[3] else result=nil if val[1]!=0 then result=val[3] else result=val[5] a=0 if a then b=1 else b=2 print( "b= ", b," n") b= 2 a=1 if a then b=1 else b=2 print( "b= ", b," n") b= 2

4 代入式を書けるようにする式として代入式も認める right '^' nonassoc UMINUS left '*' '/' left '+' '-' right '=' rule target: exp assign /* none */ result = 0 exp: exp '+' exp result += val[2] exp '-' exp result -= val[2] assign assign : IDENT '=' exp result = do_assign( val[0], val[2] ) この現象が起こることを確認してください思わしくない理由 "then" 部分も "else" 部分も必ず構文解析を行い構文解析に成功すれば意味解析 ( インタープリターでは実行 ) もしてしまう if 全体の値は正しいのだが副作用がある部分 ( 代入!) はおかしくなるまた効率が悪い ( 計算する必要のない計算を行ってしまう ) if val[1]!=0 then result=val[3] else result=nil if val[1]!=0 then result=val[3] else result=val[5] レポート課題 6 calc.y つまり電卓形式のプログラムではループ (while ループ for ループ until ループ他 ) を実装することは難しい理由を説明して下さいレポート課題 7 練習問題 6 intp.y を動かしてみてくださいそして次の確認と改善をして下さいコマンドラインからファイル名を読むようにして下さい if then else の構文が複数行に渡ることを強制しています一行内に書いてもよいようにして下さい ( 山勘を働かせて ) べき乗 (^) を導入してください注意 : FuncallNode.new を呼ぶときのべき乗の関数名は ^ ではなく ** ですファイルの読み込み begin tree = nil if ARGV.length>=1 then fname = ARGV[0] 変更です else fname = 'src.intp' File.open(fname) f tree = Intp::Parser.new.parse(f, fname) tree.evaluate rescue Racc::ParseError, Intp::IntpError, Errno::ENOENT raise #### $stderr.puts "#File.basename $0: #$!" exit 1 べき乗 expr: expr '^' expr result = FuncallNode.new(@fname, val[0].lineno, '**', [val[0], val[2]]) nonassoc UMINUS right '^' left '*' '/' left '+' '-' nonassoc EQ

5 If-then-else-: 失敗ではないが if_stmt : IF stmt THEN EOL stmt_list else_stmt END val[1], val[4], val[5] ) IF stmt THEN stmt_list else_stmt END 追加した val[1], val[3], val[4] ) shift/reduce conflict がたくさん出るというのは stmt_list から EOL stmt EOL という形が導出され追加した部分からももとからある部分からも同じものが生成されうるすなわち曖昧な文法になっているからである stmt_list : result = [] stmt_list stmt EOL result.push val[1] stmt_list EOL If-then-else-: 失敗ではないが else_stmt : ELSE EOL stmt_list result = val[2] result = nil ELSE stmt_list 追加した result = val[1] shift/reduce conflict がたくさん出るというのは stmt_list から EOL stmt EOL という形が導出されるすなわち曖昧な文法になっているからである If-then-else- つまり逆に ( つまりこの問題の原因を逆手にとり ) stmt_list が空文を許すように定義されているため if_stmt と else_stmt で EOL を落とすだけでよい! これで万事解決かというとそうでもない : if then a=1 else というように else の左側に (EOL なしに ) 文を書くことはできないこれは stmt_list の定義によると stmt_list の最後は必ず EOL でなければならないからであるつまり a=1 else などとするには stmt_list の定義を書き換えて最後に EOL が来る必要をなくせばよい if_stmt : IF stmt THEN stmt_list else_stmt END val[1], val[3], val[4] ) else_stmt : ELSE stmt_list result = val[1] result = nil stmt_list : result = [] stmt result=[val[0]] stmt_list EOL stmt result.push val[2] stmt_list EOL

parser.y 3. node.rb 4. CD-ROM

1. 1 51 2. parser.y 3. node.rb 4. CD-ROM 1 10 2 i 0 i 10 " i i+1 3 for(i = 0; i