Mitzyuki's Blog

awk を利用した構文解析ツール

友人の awk (1) の勉強支援の第 2 段。 今回はちょっと複雑な処理なので追うのが大変かも?
このスクリプトは随分以前(1996年頃)に作成したのだが、 プログラムによって微妙に異る複数の設定ファイルの中身を 解析するために作成したそこそこ汎用の構文解析機だ。 本来は perl (1) などで記述したかったのだが、 よんどころない事情で awk (1) により実装した。

以下に示す構造の状態遷移テーブルで状態(status)とキーワード(token)を定義し、 それぞれの status の時に出現する入力データ中の token により 定義されていてば外部コマンドを実行して次の status への遷移を繰り返す。

状態遷移デーブルは １カラム目が '#' の行、タブ、 スペースのみの行は無視する。
`%syntax' で始まる行が token の定義となり、 次の行以降が status の時に出現する token 毎の定義で、 実行するコマンドと遷移する status、 もしくはシンタックスエラー(error)を記述する。
予約された状態値として初期状態を示す `start'と エラー状態を示す `error' が定義されており、 エラー状態では標準エラー出力にメッセージを出力後終了する。
オプションとして開始時に 1 度だけ実行される初期処理コマンドを `%start' で始まる行に、 終了時に 1 度だけ実行される終了処理コマンドを `%end' で始まる行にそれぞれ定義できる。

%syntax	token1	token2	...	*
start	status1:command1	error	...	status2
status1	status3:command3	error	...	statusN:commandN
	:
statusN	error	error	...	start
%start command parm ....
%end command parm ....

status 定義行ではその status に遷移した際に実行するコマンドを `:' に続けて記述でき、 コマンドの引数には以下の特殊文字が指定できる。 全ての特殊文字の置き換えを終了するとシェルを通してコマンドを実行する。

%

現在のトークンに置き換えられる

,

スペースに置換えられる

$0

直前のコマンドのリターン値に置き換えられる

$1 〜 $N

このコマンドの第 3 引数以降に置き換えられる

実際に使用した状態遷移テーブルの例を示す。 下で示す形式の設定ファイルの解析を実施するためのもので、 開始状態から入力データに応じて状態値を遷移させながら解析処理を実施する。

# 最初に実行されるコマンド
%start      ${path}/do.start

# 最後に実行されるコマンド
%end        ${path}/do.end $0

# token 定義
%syntax     {           }      ,           =          *

# 状態遷移テーブル
start       error       error  error       error      name:${path}/do.name,%,$0,$1,$2
name        keyword     error  error       error      error
keyword     error       start  error       error      continue:${path}do.keyword,%,$0,$1,$2
continue    error       error  error       equal      error
equal       error       error  error       error      next:${path}/do.val,%,$0,$1,$2
next        error       start  keyword     error      error
	

解析させた設定ファイルの形式。

名称1 {
	キーワード1 = 値1,
	キーワード2 = 値2,
	  :
	キーワードN = 値N
}

  :

名称M {
	キーワード1 = 値1,
	キーワード2 = 値2,
	  :
	キーワードN = 値N
}
	

この定義ファイルの解析を実行すると 以下の順にコマンドを実行する事と等価な処理が実施できる。

$ ${path}/do.start
$ ${path}/do.name 名称1 $? 引数1 引数2
$ ${path}/do.keyword キーワード1 $? 引数1 引数2
$ ${path}/do.val 値1 $? 引数1 引数2
$ ${path}/do.keyword キーワード2 $? 引数1 引数2
$ ${path}/do.val 値2 $? 引数1 引数2
    :
$ ${path}/do.keyword キーワードN $? 引数1 引数2
$ ${path}/do.val 値N $? 引数1 引数2
    :
$ ${path}/do.name 名称M $? 引数1 引数2
$ ${path}/do.keyword キーワード1 $? 引数1 引数2
$ ${path}/do.val 値1 $? 引数1 引数2
$ ${path}/do.keyword キーワード2 $? 引数1 引数2
$ ${path}/do.val 値2 $? 引数1 引数2
    :
$ ${path}/do.keyword キーワードN $? 引数1 引数2
$ ${path}/do.val 値N $? 引数1 引数2
$ ${path}/do.end $?
    

そしてスクリプト本体。 今見返すと冗長な記述などもあるが敢えてそのままにしておく。

  1#!/bin/sh
  2#
  3# Copyright (c) 1996 Mitzyuki IMAIZUMI, All rights reserved.
  4#
  5# $Id: parser,v 1.7 1996/02/01 19:33:18 mitz Exp $
  6#
  7# 名称 
  8#   parser - 状態遷移テーブルに基づいてシンタックスをチェック
  9#
 10# 構文
 11#   parser config input [引数…]
 12# 
 13# 引数
 14#   config
 15#       状態遷移テーブル
 16#   input
 17#       入力ファイル
 18#   引数…
 19#       各状態で実行するコマンドの引数
 20#
 21
 22# パラメタチェック
 23test $# -lt 2 -o ! -f $1 -o ! -f $2 && exit 255
 24
 25trap '' 1 2 3 5 9 13 15
 26
 27conf=${1}; file=${2}; shift 2
 28
 29for i
 30do
 31    parm="${parm},${i}"
 32    shift
 33done
 34
 35# %syntax 行から token を取得(最後の token は除外
 36token=`
 37    awk '{
 38        if($1 == "%syntax"){
 39            for(i=2; i<NF; i++)
 40                printf("%s", $i);
 41            exit
 42        }
 43    }' ${conf}`
 44
 45# 入力ファイルの token 前後にスペースを付加する
 46sed 's/['${token}']/ & /g' ${file}    |
 47
 48awk '
 49    #
 50    # 初期処理
 51    #   状態遷移テーブルのリード
 52    #
 53    BEGIN{
 54
 55        argc = split("'${parm}'", argv, ",");       # 引数を格納
 56        argv[1] = 0;
 57
 58        while(getline < "'${conf}'" > 0){
 59            if(/^#/ || /^[ \t]*$/)                  # コメント行/空行
 60                continue;
 61            if($1 == "%start"){                     # 初期処理定義行
 62                $1 = "";
 63                prolog = $0;
 64            }
 65            else if($1 == "%end"){                  # 終了処理定義行
 66                $1 = "";
 67                epilog = $0;
 68            }
 69            else if($1 == "%syntax")                # トークン定義行
 70                for(i=2; i<NF; i++)
 71                    item[i-1] = $i;
 72            else                                    # 状態遷移定義行
 73                for(i=2; i<NF; i++)
 74                    if(p = index($i, ":")){
 75                        data[$1 item[i-1]] = substr($i, 0, p-1);
 76                        command[$1 item[i-1]] = substr($i, p+1);
 77                    }
 78                    else
 79                        data[$1 item[i-1]] = $i;
 80        }
 81        if(prolog != "") 
 82            argv[1] = exec(prolog, "");
 83
 84        status = "start";
 85
 86    }
 87
 88    #
 89    # トークンチェック
 90    #
 91    function  isitem(item, token,       i)
 92    {
 93
 94        for(i in item)
 95            if(item[i] == token)
 96                return 1;
 97
 98        return 0;
 99
100    }
101
102    #
103    # コマンド実行
104    #
105    function  exec(command, token,      buf, i)
106    {
107
108        gsub("%", token, command);
109        for(i=0; i<argc; i++){
110            buf = sprintf("\\$%d", i);
111            gsub(buf, argv[i+1], command);
112        }
113        gsub(/,/, " ", command);
114
115        i = system(command);
116        close(command);
117
118        return i;
119
120    }
121
122    #
123    # メイン処理
124    #
125    {
126
127        # コメント行スキップ
128        if(/^#/) 
129            continue
130
131        for(i=1; i<NF; i++){
132            if(isitem(item, $i)){
133                format = command[status $i]
134                status = data[status $i]
135            }
136            else{
137                format = command[status]
138                status = data[status]
139            }
140            if(status == "error"){
141                printf("%s: %d: syntax error \"%s\"\n",
142                    "'${file}'", NR, $i) | "'cat' >2"
143                ret = 255
144                exit
145            }
146            else if(format != "")
147                if(format == "exit"){
148                    ret = argv[1]
149                    exit 
150                }
151                else
152                    argv[1] = exec(format, $i)
153        }
154
155    }
156
157    #
158    # 終了処理
159    #
160    END{
161        if(epilog != "")
162            exec(epilog, "")
163
164        exit ret
165    }
166'