Feb 25, 2011
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'
Edit this entry...
wikieditish message: Ready to edit this entry.
A quick preview will be rendered here when you click "Preview" button.
