回 6-2 道 6 言語と処理系
構文解析は、字句解析で切り出した並びが文法に合っているかを調べ、合っていれば木の形 (構文木、抽象構文木) に組み立てる処理です。1 + 2 * 3 なら、掛け算を先にまとめた ("+", 1, ("*", 2, 3)) という木になり、木を葉からたどると 7 が出ます。閉じない括弧のように文法に合わない並びは、実行の前に構文エラーとして止めます。
字を字句に切る段と、字句を木に組む段を分け、掛け算が先になる理由や閉じない括弧がどの段で決まるかを切り分けられるようになります。
文 ゆめさくコード編集部 公開 2026年10月27日 更新 2026年10月27日 出典を確かめた日 2026年10月27日
1 + 2 * 3 が 式を「字句」に切り、文法に沿って「木」に組み立てるから分かります。掛け算を先にまとめた木ができれば、あとは木を下からたどるだけで 7 が出ます。木を組む作業を構文解析 (こうぶんかいせき、パーシング) と呼び、その前に字を字句に切る作業を字句解析と呼びます。
コンピュータに届くのは、1、空白、+ と並んだ字の列にすぎません。左から順に計算すると、1 + 2 で 3、それに 3 を掛けて 9 になってしまいます。
構文 (こうぶん) は、語をどう並べると正しい文になるかの決まりです。プログラムの言語にも構文があり、処理系 (プログラムを読んで動かす仕組み) はまず構文に沿ってコードを読み分けます。
道 6 では、小さな言語「ちび電卓」を 4 回 で育てます。前の 6-1 では、字の並びを「数」「名前」「記号」に分ける決まりを正規表現で書きました。この回はその続きで、同じ 3 種類に切った字句を木に組み、計算して 7 を出します。
字句解析と 字句解析は字の列を意味のある最小の単位に切り、構文解析はその並びを文法に沿って木に組みます。処理系はこの 2 段 のあとで意味を調べ、実行や翻訳に進みます。
段 受け取る物 渡す物 ここで 字句解析 字の列 字句 (トークン) の列 使えない字 構文解析 字句の列 構文木 閉じない 意味解析 構文木 調べ終えた木 型の
意味解析は、木の形は正しくても意味が通らない所を探す段で、6-4 で扱います。
字句解析は 字句解析は、字の列を「数」「名前」「記号」のような種類に切り分け、空白を捨てる段です。切り出した 1 つ を字句 (切る部品を字句解析器 (レキサー) と呼びます。
ちび電卓では、字句を (種類, 値) の組で表します。種類は次の 4 つ です。
種類 値 例 num 整数 ("num", 12)name 英小文字の並び ("name", "x")op 1 字の記号 ("op", "+")end 値なし ("end", None)
end は「ここで終わり」の印で、構文解析が式の終わりを確かめるのに使います。
字句解析では、12 を 1 と 2 の 2 つ ではなく、数の 12 という 1 つ の字句にまとめます。正規表現の \d+ は続く数字をできるだけ長く取るので、これが自然にできます。
文法は 構文解析の決まりは、文法として書き出します。書き方の代表が BNF (バッカス・ナウア記法) で、「左の名前は、右の並びでできている」という規則を並べます。ちび電卓の文法は次の 3 行 です。
電卓の文法 (BNF を広げた書き方)
式 ::= 項 (("+"|"-") 項)*
項 ::= 因子 (("*"|"/") 因子)*
因子 ::= 数 | "(" 式 ")"| は「または」、( )* は「0 回 以上くり返す」です。式は項を + か - でつないだ物、項は因子を * か / でつないだ物、因子は数か、括弧で囲んだ式です。
式や項のように、さらに分けられる名前を非終端記号、数や + のような字句を終端記号と呼びます。左に名前を 1 つ だけ置く規則の集まりを、文脈自由文法と呼びます。
この文法には、掛け算が先という決まりがすでに入っています。+ は式の段でつなぎ、* はその下の項の段でつなぐので、* でつないだ塊が先にでき、+ はその塊どうしをつなぎます。優先順位は、文法の段の深さで表すのです。
因子の中に式が出てくるので、括弧がいくつ入れ子になっても同じ 3 行 で読めます。
構文木と 構文解析の出す木を構文木と呼びます。規則を当てはめた跡を全部残すのが具体構文木、計算に要る形だけを残すのが抽象構文木 (AST) です。
木 残す物 (1 + 2) * 3 の括弧 具体構文木 規則の 字句として残る 抽象構文木 (AST) 演算と、その左右 残らない。
ちび電卓の抽象構文木は、タプルで書きます。数は int のまま、2 項の演算は (演算子, 左, 右) です。1 + 2 * 3 は ("+", 1, ("*", 2, 3)) で、根が +、その右の子が * の木です。
ちび電卓の木では、葉が数、枝分かれする所が演算子です。
作り方は 構文解析器 (パーサー) の作り方は、大きく 2 つ に分かれます。
作り方 進め方 代表 トップダウン 根 (式) から 再帰下降、 ボトムアップ 字句を LR 法、
この回で書くのは、トップダウンの再帰下降構文解析です。文法の 1 行 を 1 つ の式の関数が項の関数を、項の関数が因子の関数を呼びます。因子の関数は括弧を見ると式の関数を呼び直すので、関数が自分の上の段を呼ぶ再帰になります。
本物の処理系もこの道具立てで動いています。Python は 3.9 から、それまでの LL(1) (左から読み、先を 1 字 句だけ見て決める作り方) の構文解析器を、PEG (トップダウンの一種) の構文解析器に替えました (PEP 617)。
動かして確かめる 1 本 目は字句解析です。正規表現で数、名前、空白でない 1 字 の 3 種類を拾い、(種類, 値) の組の列を作ります。
動かす 字句解析 1 + 2 * 3 を字句に切る
実行すると、次の通りに出ます
('num', 1)
('op', '+')
('num', 2)
('op', '*')
('num', 3)
('end', None)
num op op name op num op end空白は捨てられ、最後に end が付きました。12*(x-3) のように空白が無くても、12 は 1 つ の num に、x は name にまとまります。
2 本 目は、字句の列を文法の 3 行 どおりの 3 つ の組み、木をたどって計算します。calc は、葉なら数をそのまま返し、演算なら左右を先に計算してから演算子を当てます。/ は整数の割り算 (//) です。
動かす 構文解析して木をたどる
実行すると、次の通りに出ます
('+', 1, ('*', 2, 3))
= 7
('*', ('+', 1, 2), 3)
= 9
('/', 7, 2)
= 31 + 2 * 3 は ("+", 1, ("*", 2, 3)) になり、計算すると 7 です。+ の右の子に * の木が入り、掛け算が先にまとまりました。(1 + 2) * 3 は根が * に替わって 9 になり、括弧は木の形に溶けて字句としては残っていません。7 / 2 は整数の割り算で 3 です。
expr が term を、term が factor を呼ぶ形は、文法の 3 行 をそのまま関数にした物です。今の factor は数と括弧だけを受け、name の字句は誤りとして止めます。足します。
calc も、葉で数が決まると値を持って戻る再帰です。下の図は階乗の例ですが、戻り方は同じです。
どこで 構文解析は、優先順位と結合の向きを文法の形で決めるので、形を取り違えるとエラーにならずに違う答えを出します。文法に合わない並びは、実行の前に構文エラーとして止めるのが役目です。
結合の 10 - 3 - 2 は、左から (10 - 3) - 2 とまとめて 5 です。同じ強さの演算子が並んだときに左からまとめることを左結合と呼びます。公式文書も、同じ段の演算子は左からまとめ、例外は累乗 (**) と条件の式だけだと書いています。
ところが文法を 式 ::= 数 ("-" 式)? のように、右へ再帰する形で書くと、10 - (3 - 2) とまとめてしまいます。次のコードは、同じ字句の列を 2 通りに組んで比べます。字句は 2 本 目の lex と同じ形で、ここでは手で並べています。
動かす 左から組むか、右から組むか
実行すると、次の通りに出ます
left 5
('-', ('-', 10, 3), 2)
right 9
('-', 10, ('-', 3, 2))
Python 5left は 5 で、Python の答えと同じです。右へ再帰した right は ("-", 10, ("-", 3, 2)) という木を作り、9 を出しました。+ や * だけで試すと、どちらの組み方でも答えが同じなので誤りに気づけません。引き算や割り算を 2 回 以上続けた式で試す必要があります。
2 本 目の expr が while のループで左へ積み上げているのは、このためです。
文法に 構文解析器のもう 1 つ の役目は、文法に合わない並びを見つけて、どこが合わないかを伝えることです。次のコードは 2 本 目と同じ字句解析と構文解析に、誤りのある式を 5 つ 渡します。
動かす 構文エラーの出し分け
実行すると、次の通りに出ます
(1 + 2 | ) が無い
1 + | 式が途中で終わる
2 * * 3 | 数が要る所に *
1 2 | 余計な字句 2
1 + 2) | 余計な字句 )どの規則のどこで食い違ったかで、エラーの文を分けました。1 2 と 1 + 2) は、式としては途中まで読めますが、読み終えたあとに字句が余るので止めます。最後に end を確かめないと、この 2 つ は余った字句を黙って捨て、途中までの木で計算してしまいます。
Python も同じで、ファイル全体を構文解析してから実行を始めます。そのため構文エラーがあると、1 行 目の print も動きません。
文法 文法の書き方によっては、1 つ の文に 2 通りの木ができてしまいます。これを曖昧な文法と呼びます。よく知られた例が、if A then if B then C else D の else が、どちらの if に付くか決まらない「ぶら下がり else」です。一般には、else をいちばん近い then (if) に付けると決めて曖昧さを消すか、エラーにします。
ちび電卓の文法は、段を分けたことで、どの式にも木が 1 通りしかできないようにしてあります。
構文解析は 仕事では、自分の読み手の木を、本物の処理系の木や答えと照らして確かめます。コードを抽象構文木にする ast モジュールが付いています。
動かす Python の構文解析器の木を見る
実行すると、次の通りに出ます
Expression(
body=BinOp(
left=Constant(value=1),
op=Add(),
right=BinOp(
left=Constant(value=2),
op=Mult(),
right=Constant(value=3))))
(1 + 2 | '(' was never closed
1 + | invalid syntaxPython の木でも、Add (足し算) の右の子に Mult (掛け算) の木が入っています。ちび電卓の ("+", 1, ("*", 2, 3)) と同じ形です。閉じない括弧は「'(' was never closed」として、実行の前に止まりました。なお公式文書は、抽象構文そのもの (木の形) が Python の版ごとに変わり得ると書いています。
確かめ方は次の通りです。
優先順位 (1 + 2 * 3) と、括弧 ((1 + 2) * 3) と、結合の向き (10 - 3 - 2) を、答えの分かっている式で試す 閉じない括弧、途中で終わる式、余る字句を渡し、エラーになることと、その文を試す 本物の処理系 (Python の ast や eval) と同じ式で答えを照らす 試験の例 (pytest の形)
def test_order():
assert calc(parse(
"1 + 2 * 3")) == 7
assert calc(parse(
"10 - 3 - 2")) == 5
def test_unclosed():
with pytest.raises(
SyntaxError):
parse("(1 + 2")設定ファイル、検索の条件式、表計算の数式のように、文字で書かれた決まりを読む所にも、同じ 2 段 があります。Python の ast の木を読めば、コードの中から決まった書き方を機械で探す道具も書けます。
この回で、ちび電卓は式を木にして計算できるようになりました。次の 6-3 では、この木にif、while の文を足し、木をたどるインタプリタで 1 から 10 の合計を出します。
関わる実例 同じ字の それまで文 (専用の構文) だった print が、ふつうのprint() に替わりました。提案の PEP 3105 は 2006年 11月 19日 に作られ、状態は Final (受け入れて実装済み) です。
PEP 3105 は、互換性の節で、今ある print の文のほとんどが Python 3.0 では正しい構文でなくなると書いています。そのうえで、同じ print ("Hello", "world") という並びが、2.x では組 (タプル) を 1 つ 出す文として読まれて ('Hello', 'world') と出し、3.0 では 2 つ の引数を渡す関数の呼び出しとして読まれて Hello world と出す例を挙げています。
崩れた前提は「同じ字の並びなら、同じ木になる」です。木は文法で決まり、文法は版で変わるので、字句が同じでも別の木になり、別の動きになります。
出典は PEP 3105 (python.org) です。
改行で 仕様 ECMAScript は、文の終わりの ; が無くても、決まった場合には構文解析の途中で ; を補うと定めています。これを自動の ; 挿入 (ASI) と呼びます。
仕様の例では、return の次の行に a + b を書くと、return; と a + b; の 2 つ の文に変えられます。a + b は返す値として扱われません。return と値の間に改行を置いてはいけない、と文法の規則で決めてあるからです。
崩れた前提は「改行は空白と同じで意味を持たない」です。構文解析が改行を見て ; を補うので、書いた人の思った木とは違う木ができます。
出典は ECMAScript Language Specification の 12.10 Automatic Semicolon Insertion (tc39.es) です。
よくある問い 正規表現だけで 括弧の入れ子が無い決まりなら、正規表現で足ります。けれども括弧がいくらでも入れ子になる式は、開いた数と閉じた数を覚えておく必要があり、正規表現の形では書けません。そのため、字句に切る所までを正規表現に任せ、入れ子を読む所は構文解析で受け持つのがふつうです。
パーサーは どちらも使われています。yacc や Bison のような生成器 (文法を渡すと解析器のコードを書き出す道具) は、文法を表として管理でき、曖昧な所を早めに知らせてくれます。手書きの再帰下降は、この回のように読みやすく、誤りの文を細かく出し分けやすいのが長所です。
日本語の 木を作る考え方は同じですが、前提が違います。プログラムの言語は 1 つ の文に木が 1 通りになるよう文法を作れますが、日本語や英語の文は、同じ文に何通りもの読み方があるのがふつうです。そのため自然言語の構文解析では、ありうる木の中から、確からしい物を選ぶ工夫が中心になります。
確認クイズ 答えだと
1 問目
ちび電卓の文法で、1 + 2 * 3 の掛け算が先にまとまる理由はどれですか。
ア 字句解析が、 イ 計算する calc が、 ウ 字句の エ * は 2 問目
このコードを動かすと何が出ますか。
木をたどって計算する
def calc(t):
if isinstance(t, int):
return t
op, a, b = t
if op == "-":
return calc(a) - calc(b)
return calc(a) * calc(b)
t = ("-", 10, ("*", 2, 3))
print(calc(t))3 問目
10 - 3 - 2 を、右へ再帰する文法で組んだときに出る答えはどれですか。
4 問目
閉じない括弧 (1 + 2 を見つけるのは、処理系のどの段ですか。
説明課題 1 + 2 * 3 が 7 になるまでを、「字句」「文法の段」「木」「葉からたどる」という言葉を使って、3〜4 文で説明してください。書いたら、下の模範解答を開いて比べてください。
あなたの説明
模範解答 模範解答を開く 自分の
まず字句解析が、1 + 2 * 3 という字の列を、数と記号の字句の列に切り、空白を捨てる。次に構文解析が、式は項を + でつなぎ、項は因子を * でつなぐという文法の段に沿って字句を組み、* の塊を + の右の子に入れた ("+", 1, ("*", 2, 3)) という木を作る。最後に木を葉からたどり、2 * 3 の 6 を先に出してから 1 を足して 7 を出す。掛け算が先になるのは、計算の順の決まりではなく、文法の段の深さが木の形を決めているからだ。
設定ファイル、
一次資料 どれも 2026年 10月 27日 に開いて、題と中身を確かめました。
