この文章は、 lisp Advent Calendar 2018 - Qiita の24日目の記事として書かれましたが、 ほとんどC言語の話です 。

CL-Yacc とは
- ネタマクロ with-c-syntax での用途
C言語の文法の微妙な点 : typedef
- typedef のパーズの例
- 回避策の一つ : The Lexer Hack
CL-Yacc と The Lexer Hack の微妙な関係
まとめ

CL-Yacc とは

CL-Yacc は、 yacc という名前が示す通り、 Common Lisp による LALR(1) パーザジェネレータの実装です。 BNF っぽいものをS式で与えるだけで、簡単にパーザを作ることが出来ます。

なんと日本語の資料もあり、このページには簡単な例も載っています。

Quicklisp でもインストールも可能で、以下でインストールできます:

(ql:quickload "yacc")

ネタマクロ with-c-syntax での用途

拙作のネタマクロ with-c-syntax では、C言語の文法をパーズするために CL-Yacc を使っており、ソースコードには C言語の構文のBNFをほぼそのまま突っ込んだ部分があったりします。

例として、このネタマクロで簡単な数式をパーズさせ、展開させてみましょう。

まずインストール:

;; ネタマクロをインストール
CL-USER> (ql:quickload "with-c-syntax")

リーダーマクロを有効化します。

;; '#{' リーダーマクロを有効化
CL-USER> (named-readtables:in-readtable with-c-syntax:with-c-syntax-readtable)

普通に計算させてみましょう。

CL-USER> #{ pprint (1 + 2 - 3 * 4); }#

-9
; No value

どのように計算しているのかを知るため、上の式の展開結果を見てみます。リードマクロ #{ の展開結果を得るには quote すればよいです。

CL-USER> '#{ pprint (1 + 2 - 3 * 4); }#
(WITH-C-SYNTAX.CORE:WITH-C-SYNTAX (:KEYWORD-CASE :UPCASE)
  PPRINT  |(|  1  +  2  -  3  *  4  |)|  |;|)

この結果を macroexpand すると、内部で CL-Yacc でパーズされ、最終的に Lisp 式になります:

CL-USER> (macroexpand *)
(LET* ()
  (DECLARE (DYNAMIC-EXTENT)
           (SPECIAL))
  (LABELS ()
    (WITH-C-SYNTAX.CORE::WITH-DYNAMIC-BOUND-SYMBOLS NIL
      (BLOCK NIL (TAGBODY (RETURN (PPRINT (- (+ 1 2) (* 3 4)))))))))
T

色々とくっついていて見辛いですが、以下の部分に、 CL-Yacc でのパーズ結果が現れていることが分かります:

(PPRINT (- (+ 1 2) (* 3 4)))

C言語の文法の微妙な点 : typedef

ここからC言語の話です。 C言語の構文解析においては、いくつかちょっと難しい点があります。

一つは有名な dangling else 問題です。 CL-Yacc でもこれは警告されますが、オプションを付けることでよしなに扱ってくれます。

もう一つは、 ISO C90 で導入された typedef です。 typedef がない時代のC言語では、字句解析は文脈に依存せず行うことが出来ましたが、 typedef の導入により出来なくなってしまいました。

typedef のパーズの例

まず、以下の C コードを考えます:

int_like_t hoge = 100;

この場合、 int_like_t は identifier, hoge も identifier です。これを C言語パーザに食わせると、 「int_like_t型は知らない」 とか 「identifier と identifier を連続させるな」 といったエラーが出ます:

$ cat typedef_test.c
int_like_t hoge = 100;

$ cc -c typedef_test.c
typedef_test.c:1:1: error: unknown type name 'int_like_t'
int_like_t hoge = 100;
^
1 error generated.

一方、以下のように typedef を付けると、無事にパーズできます:

$ cat typedef_test_2.c
typedef int int_like_t;
int_like_t hoge = 100;

$ cc -c typedef_test_2.c

$ ls typedef_test_2*
typedef_test_2.c    typedef_test_2.o

一行目に書いた typedef により、 int_like_t は typedef された型名 (typedef-name)であると意味が変わってしまいました。これにより、エラーなくコンパイルが通るようになりました。

ここで起こっていることは、 全く同じ字面の token なのに、その前に typedef が現れていたかによって解釈が変わってしまう ということです。

typedef がないC言語ならば、上の例における int_like_t も hoge も identifier であると、 字句解析の時点で 確定できるのですが、 typedef があると構文解析の結果によって後の token の意味が変わるため、このような決め打ちは出来なくなってしまいます。

回避策の一つ : The Lexer Hack

この問題の対処策の一つとして The lexer hack というものがあります。

この手法は、構文解析で分かった typedef-name を字句解析器に横流しし、字句解析器で identifer と typedef-name とを識別できるようにするというものです。詳細は、リンク先の記事を参照して下さい。

CL-Yacc と The Lexer Hack の微妙な関係

ネタマクロでのバグ

さて、拙作のネタマクロ with-c-syntax でも、無駄に typedef をサポートしており、以下のコードが通ります:

CL-USER> #{
int func () {
  typedef int int_like_t;
  typedef short int sint_like_t;

  int_like_t hoge = 1;
  sint_like_t fuga = 2;

  return hoge + fuga;
}
}#
NIL

CL-USER> (func)
3

この typedef のサポートは、上でリンクした The lexer hack を使いました。

しかし、テストしていると、少し宣言の順番を変えた以下のコードが通らないという状況が見つかりました:

CL-USER> #{
int func () {
  typedef int int_like_t;
  int_like_t hoge = 1;

  typedef short int sint_like_t;
  sint_like_t fuga = 2;

  return hoge + fuga;
}
}#

以下のエラーになってしまったのでした:

with-c-syntax parse error. yacc error is
Unexpected terminal WITH-C-SYNTAX.CORE::{ (value WITH-C-SYNTAX.CORE::{). Expected one of: (=
                                                                                           WITH-C-SYNTAX.CORE::|,|
                                                                                           WITH-C-SYNTAX.CORE::|;|)
   [Condition of type WITH-C-SYNTAX.CORE::WITH-C-SYNTAX-PARSE-ERROR]

「順番を変えただけで通らないとか、そんなのありえる？？？」と悩まされました。

原因

原因は、 CL-Yacc がこの部分のパーズする時の処理にありました。

  typedef int int_like_t;
  int_like_t hoge = 1;

CL-Yacc は、上の一行目 typedef int int_like_t; を読み、 さらに次の token (int_like_t) を先読みしてから ユーザー定義のハンドラに処理を渡すようなのです。

以下のような挙動になっていました:

CL-Yacc は、 typedef int int_like_t; までを字句解析器から読む。
CL-Yacc は、さらに二行目の int_like_t を字句解析器から読む。 このとき、まだ int_like_t token は typedef されていないとされ、 int_like_t は identifier として読まれる。
CL-Yacc は、先読み結果を cl-yacc 関数のローカル変数に保持する。
with-c-syntax は一行目の typedef の処理を行い、int_like_t が次に読まれると typedef-name だと返すようにする。
CL-Yacc は、 int_like_t の部分を読み直したりはしない (identifier とみなし続ける）。二行目の続きの hoge = 1; の箇所を字句解析器から読む。
CL-Yacc は、 int_like_t という identifier と、 hoge という identifier が連続していると思って、最終的にエラーになる。

がんばって 4. の段階で字句解析器に仕込みをしているのですが、それが使われることはないので、エラーとなってしまいました。並び順が違う例でエラーが出ないのは、当該 token が先読みされていないためでした。

この問題の対処は、CL-Yacc と the lexer hack の組み合わせを使う限り、難しそうでした。ローカル変数やクロージャに閉じられた変数を外部から書き換えることは、原則的には出来ないので、 typedef の処理結果を CL-Yacc の関数のローカル変数に反映するのは非常に難しいです。パーズエラーも、 typedef が原因だと明確に示されるものではなく、普通の文法エラーと区別が付かないものでした。「typedef の次の行だけ typedef 名が使えない」というのは、あまりにおかしな制限と思われました。

無理やり解決

ネタマクロ with-c-syntax では、この問題を荒い hack で突破しました。並び順が違う例でエラーが出ない点に着目し、 「とにかく一行はさめば何とかなるだろ」 という雑な考えを実行しています。

このコード片を見ると・・

  typedef int int_like_t;
  int_like_t hoge = 1;

パーザに渡す前に、間になにもしない行を挟み込みます:

  typedef int int_like_t;
  void;            // この行を勝手にはさむ。
  int_like_t hoge = 1;

すると、 typedef の後で先読みされる token は、予約語 void になり、これは字句解析器の段階で意味が確定しています。この後、パーザが次の行を読む時には、無事に the lexer hack が発動しており、なんとか問題が回避できます。

実装部分はここです。

まとめ

ネタを実装するだけなのに、妙に大変でしかも取り回しの効かない策を捻りだしたという話でした。最近、このネタマクロを少し記事にしたら、一部でちょっとウケてたようなので、昔の記憶を探って記事にしてみた次第です。

一方、 CL-Yacc の公式には CL-Yacc was originally written to compile a grammar for a superset of the C programming language なんて書いてあるので、字句解析器をいじるのと相性が悪いだけで、別の方法を使えばよかったのかもしれません。

y2q_actionman’s ゴミクズチラ裏

内向きのメモ書きを置いてます

CL-Yacc と C言語文法の微妙な関係