ちび電卓作ってみた

Scheme

Chicken Schemeで構文解析はできるのか検証しました。
自分でパーサ書くのは死ぬほどしんどいというのはJavaで体験済みなのでライブラリを探してみます。

アーッ yacc無かった！

yaccがあれば楽になると期待してみたところ残念ながらありませんでした。
あれはあるのにこれは無いというeggライブラリのこの微妙な充実度。Zipのライブラリならともかくさすがにパーサジェネレータを書く気にはなれません。
・・・と思ったところで発見！しかもYaccと同じLALR(1)の構文解析器。よかった！
後もうひとつ、字句解析器が必要です。Cでいうyylex()あたり。
字句解析のほうは死ぬほどまで大変ではないので手書きでも大丈夫・・・
ところでrubyはどうやってるのか？
Rubyソースコード完全解説の第10章あたりにyylex()の解説があります。

yylex()はとても長い。現在1000行以上ある。そのほとんどが巨大な switch文一つで占められており、文字ごとに分岐するようになっている。まず一部省略して全体構造を示す。

・・・／(^o^)＼
大丈夫とか絶対嘘ですよ、これ。

というわけで

今回は構文解析と字句解析に lalr と silex の２つのエッグを使用します。
chicken-install -k lalr silex
どっちのライブラリもドキュメントが不十分なのでコードを読む気でかかりましょう。
ちび電卓のファイルは３つに分割しました。

  1. 字句解析用の定義ファイル calc.l
  2. 構文解析用の定義と両解析器を生成する prepare.scm
  3. ちび電卓の本体 calc.scm
; calc.l - An example for SILex
; 2011 moondial0.net
; (yycontinue) yytext yyline yycolumn yyoffset
; See Also: http://api.call-cc.org/doc/silex

space   " "|"　"
vblank  "\n"|"\r"|"\r\n"
digit   [0123456789]+
symbol  "+"|"-"|"*"|"/"|"="
letter  [a-zA-Z]+

%%

{digit} (cons 'NUMBER (string->number yytext))
{symbol} (string->symbol yytext)
{letter} (cons 'ID (string->symbol yytext))
{vblank} (list 'NEWLINE)
<<ERROR>> (make-tok <<ERROR>>-tok yytext yyline yycolumn)
<<EOF>> (print "---File Border Line---")'*eoi*

; -*- coding: sjis -*-
; prepare.scm
; 
(use silex) ;; 字句解析器生成器
(print "字句解析器生成中...")
(lex "calc.l" "calc.lex.scm" 'counters 'all) ;; 字句解析器生成
;;第四引数が'noneならyytextのみ 'lineならyytextとyyline
;;'allならyytext,yyline,yycolumn,yyoffsetが取得できる

(use lalr) ;; パーサ生成器 See Also: http://api.call-cc.org/doc/lalr
(print "構\文解析器生成中...")
;; 電卓用パーサを生成
(define calc-parser
	(lalr-parser
		;; *オプション*
		;; 同名のパーサをファイルに書き出す
		(output: calc-parser "calc.syntax.scm")
		;; *終端記号の定義*
		(ID NUMBER NEWLINE LPAREN RPAREN
			(nonassoc: =) ;; 非結合
			(left: + -) ;; 左結合
			(left: * /) ;; 上より優先順位が低い
			(nonassoc: -@) ;; 単項演算子のマイナス符号
		)
		;; *構文規則の定義*
		;(lines
		;	(lines line) : (print "継続行 " $2)
		;	(line) : (print "開始行 " $1)
		;)
		;(line
		;	(NEWLINE) : (print "空行")
		;	(assign NEWLINE) : (begin (print "宣言行 " $1) $1)
		;	(expr NEWLINE) : (begin (print "式の行" $1) $1)
		;	(error NEWLINE) : (begin (print "エラー行") #f)
		;; NEWLINEまでに構文エラーが起きたら発動
		;)
		(lines
			(lines NEWLINE line) : (begin(print "継続行")(append $1 (list $2)))
			(line) : (begin (print "開始行") (list $1))
			(error NEWLINE) : (print "エラー行")
		)
		(line
			(NEWLINE) : (begin (print "Exit!") (exit))
			(assign) : (begin (print "宣言 " $1) $1)
			(expr) : (begin (print "式 " $1) $1)
		)
		(assign (ID = expr) : (add-binding $1 $3)) ;; 代入
		(expr
			(NUMBER) : (begin (print "number: " $1) $1)
			(ID) : (get-binding $1)
			(expr + expr) : (+ $1 $3)
			(expr - expr) : (- $1 $3)
			(expr * expr) : (* $1 $3)
			(expr / expr) : (/ $1 $3)
			(- expr (prec: -@)) : (- $2)
			(LPAREN expr RPAREN) : $2
		)
	)
)
(print "コンパイル中...")

; -*- coding: sjis -*-
; calc.scm
;
(print "Hello, lexer!")
(use silex) ;; 字句解析器生成器
(include "calc.lex.scm")
(define lexer-error error)
(use lalr-driver) ;; 構文解析実行器 lr-driverの実装
(include "calc.syntax.scm")
;; 字句解析器
;(lexer-init 'string|port|procedure "")
;; 電卓用環境
(define *env* (list (cons '$$ 0)))
(define (add-binding var val)
  (set! *env* (cons (cons var val) *env*))
  val)
(define (get-binding var)
  (let ((p (assq var *env*)))
    (if p
        (cdr p)
        0)))
(define (init-bindings)
  (set-cdr! *env* '())
  (add-binding 'cos cos)
  (add-binding 'sin sin)
  (add-binding 'tan tan)
  (add-binding 'expt expt)
  (add-binding 'sqrt sqrt))
;; メイン
(define (parser-error . args)
	(print "ParseError: "args))
	;(display "parser error: ")(for-each display args)(newline))
(define (calc)
	(call-with-current-continuation (lambda (k)
		(print "ちび電卓 on チキンScheme")
		(init-bindings)
		;(lexer-init 'port (open-input-file "testfile"))
		(lexer-init 'port (current-input-port))
		;(lexer-init 'procedure read)
		(calc-parser lexer parser-error)
	))
)
(calc)

コンパイル・実行は

csc -v -extend prepare.scm calc.scm && calc

です。
開発中にlexerを(read)にして遊んだときの記録も残しておきます。

#;24> (calc-parser read parser-error)
(NUMBER . 10)
number: 10
+
(NUMBER . 20)
number: 20

*eoi*
ParseError: (Syntax error: unexpected end of input)
#f
#;25> (calc-parser read parser-error)
10
ParseError: (Syntax error: invalid token:  10)
#f
#;26> (calc-parser read parser-error)
(NUMBER . 10000)
number: 10000
+
(NUMBER . 20)
number: 20
NEWLINE
式の行10020
開始行 10020
*eoi*
#;27> (calc-parser read parser-error)
NEWLINE
空行？
開始行 #<unspecified>
*eoi*
#;28> (calc-parser read parser-error)
(NUMBER . 10)
number: 10
(ID . "a")
ParseError: (Syntax error: unexpected token :  (ID . a))
NEWLINE
エラー行
開始行 #f
*eoi*
#;29> (calc-parser read parser-error)
NEWLINE
空行？
開始行 #<unspecified>
NEWLINE
空行？
継続行 #<unspecified>
NEWLINE
空行？
継続行 #<unspecified>
*eoi*

(lexer-init 'port (current-input-port))
(lexer)
でlexerの動作も確認できました。
実際に動かしてみます。

C:\>csc -v -extend prepare.scm calc.scm&&calc
"C:\mingw\bin\chicken.exe" "calc.scm" -output-file "calc.c" -extend prepare.
scm
字句解析器生成中...
構文解析器生成中...
コンパイル中...
"gcc" "calc.c" -o "calc.o" -c  -fno-strict-aliasing -fwrapv -DHAVE_CHICKEN_C
ONFIG_H -DC_ENABLE_PTABLES -Os -I"C:/mingw/include/chicken"
rm calc.c
"gcc" "calc.o" -o "calc" -Wl,--enable-auto-import -L"C:/mingw/lib" -lchicken
 -lm -lws2_32
rm calc.o
Hello, lexer!
ちび電卓 on チキンScheme
10
number: 10
式 10
開始行
10+10
number: 10
number: 10
式 20
継続行
999999*99999/8
number: 999999
number: 99999
number: 8
式 12499862500.125
継続行
a=10000
number: 10000
宣言 10000
継続行
a*a*a
式 1000000000000.
継続行

Exit!