中置記法からS式への変換

Scheme 30分プログラム

30分プログラム、その727。中置記法からS式への変換。

きっと中置記法から逆ポーランド記法への変換のノリでスタックをいい感じに使ってやればできる気がします。ただ、そのやり方を思い付けなかったので、再帰降下構文解析でパースしてます。
再帰降下型パーサぐらいすぐ書けるだろ、と思っていたんですけど意外と難しかったです。優先度とか結合方向とかもう嫌です。あと、再帰降下型パーサをベタ書きしたのはこれが初めです。いつもはParsec的なライブラリを構築してから、パーサを作ってるので。

使い方

gosh> (infix->sexp '(1 + 2 * 3 / 4))
(+ 1 (/ (* 2 3) 4))

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; infix.scm -
;;
;; Copyright(C) 2010 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2010/01/26 19:32:11
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use util.match)

(define (make-stream xs)
  (list xs))
(define (peek xs)
  (caar xs))
(define (next! xs)
  (let1 x (peek xs)
	(set! (car xs) (cdar xs))
	x))
(define (empty? xs)
  (null? (car xs)))

(define (many-factors! x xs)
  (if (empty? xs)
      x
      (case (peek xs)
	[(+ -) (let* ([op (next! xs)]
		      [f  (factor! xs)])
		 (many-factors! (list op x f) xs))]
	[else x])))

(define (expr! xs)
  (let1 f (factor! xs)
    (many-factors! f xs)))

(define (many-terms! x xs)
  (if (empty? xs)
      x
      (case (peek xs)
	[(* /) (let* ([op (next! xs)]
		      [t  (term! xs)])
		 (many-terms! (list op x t) xs))]
	[else x])))

(define (factor! xs)
  (let1 t (term! xs)
     (many-terms! t xs)))

(define (term! xs)
  (cond
   [(eq? '|(| (peek xs))
    (next! xs)
    (let1 e (expr! xs)
	  (if (eq? '|)| (next! xs))
	      e
	      (error "syntax error")))]
   [(number? (peek xs)) (next! xs)]
   [else (error "syntax error")]))

(define (infix->sexp xs)
  (expr! (make-stream xs)))

参考