LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@takayoshi1968(なんば たかよし)

構文解析アルゴリズム - ①導入編

Last updated at Posted at 2025-08-23

はじめに

内容について

現代のソフトウェア開発は、高水準のプログラミング言語とその処理系に大きく依存しています.
その処理系の中核をなす技術の一つが構文解析です.
本記事では、主要な構文解析アルゴリズムについて、その仕組みと特徴を解説します.

ただし、字句解析には深入りせず、意味解析には触れません.
また、形式言語理論などについては前提知識と見なし、その詳細について説明することはありません.

誤り回復もまた構文解析器の主要トピックですが、今回の記事では触れません.
登場する構文解析器は、構文エラーを検出した場合にその事実のみを報告します.

目次、あるいは構想

執筆開始時点ではいろいろ書くつもりでしたので、導入編とそれ以降で記事を分割しています.
この記事投稿時点では下向き構文解析を書いたところで、続きは未定です.

諸注意

説明用のソースコードには Rust を使用します.
正確を期してはいますが、筆者は専門家ではなく、誤りを含む可能性があります.
内容を鵜呑みにせず、必ず自身で検証されることを望みます1.

構文解析の処理としては、文法を受け取ってパーサを返す関数を書くべきですが、説明用のコードは簡単のためトークン列と文法を受け取って構文木を返す関数としています.

記事中で使用する記号や構造体などについて

諸定義

記号列

記号の集合 $\Sigma$ の元を 0 個以上並べて得られる順序列を記号列と呼ぶ. 特に、長さ 0 の記号列は空列といい、 $\epsilon$ で表す.
$\Sigma$ から作られる記号列全体は $\Sigma^\star$ で表す. ここで、記号 $^\star$ はクリーネ閉包(Kleene star)を求める演算子である.
記号列 $w \in \Sigma^\star$ に含まれる記号の数(より厳密には、$w$ に含まれる記号の位置の数)を記号列 $w$ の長さと呼び、$|w|$ で表す.
記号列上の位置は、0 始まりのインデックスで表現される.
$w \ z$ と書くことで、$w, z \in \Sigma^\star$ の連結を表す. n.b. $w \ z \in \Sigma^\star$.
記号列 $w, w_1, w_2 \in \Sigma^\star$ が次を満たすとき、$w_1$ を $w$ の接頭辞、$w_2$ を $w$ の接尾辞と呼ぶ.

w = w_1 \, w_2

n.b. $|w| = |w_1| + |w_2|.$

あまり標準的ではないが、次の記法を用いる.

\begin{align*}
w:n =& \text{「$w\,$の先頭 $n$ 文字からなる接頭辞」} \\
    =& \begin{cases}
       w_1 & \text{if} \ w = w_1 \, w_2 \text{, and } |w| \ge n \\
       w   & \text{if} \ |w| \lt n \\
       \end{cases} \\
       & w \in \Sigma^\star,\ n \in \mathbb{N} \\
w[n..m) =& \text{「$w$ の位置 $n$ から $m-1$ までの部分列」} \\
        =&\ w':(m-n) \\
    \text{where} \quad & w = (w:n) \, w' \\
                & w \in \Sigma^\star\\
                & n, m \in \mathbb{N},\ n \lt m
\end{align*}

$n$ ないし $m+n$ が $|w|$ より大きい場合の定義には注意されたい.

例
abc:2 = ab
abc:4 = abc // |abc| < 4
ε:5 = ε // |ε| = 0 < 5

abc[1..2) = b
abc[1..100) = bc
abc[20..100) = ε

文法

以下、単に文法と言った場合は文脈自由文法を指す.
文脈自由文法 $G$ を次のような4つ組として定める.

G = ( N, \Sigma,  S, P )

ここで、

  • $N:$ 非終端記号からなる有限集合
  • $\Sigma:$ 終端記号からなる有限集合. $(N \cap \Sigma = \varnothing)$
  • $S \in N:$ 開始記号
  • $P:$ 生成規則からなる有限集合. 生成規則とは、$: A \in N, \alpha \in (N \cup \Sigma)^\star$ を用いて $A \rightarrow \alpha$ と書けるもの.

生成規則 $A \rightarrow \alpha$ の $A$ の方を左辺や頭部と呼び、$\alpha$ の方を右辺や本体と呼ぶ.
$N \cup \Sigma$ の元は文法記号、$(N \cup \Sigma)^\star$ の元は文法記号列と呼ぶ.

$\Sigma^\star$ の元を文と呼ぶ. また、文法 $G$ の生成する文全体の集合を $L(G)$ と書く.
構文解析の中では文としてトークン列を用いる.

簡単のため、特に指定がない場合、不要な記号や生成規則を含まない文法のみを扱う.
例として、次の文法では非終端記号 $C$、終端記号 $c$、生成規則 $C \rightarrow c$ が不要である.

\begin{align*}
G =&\ (N, \Sigma, S, P) \\
N =&\ \{ S, A, B, C \} \\
\Sigma =&\ \{ a, b, c \} \\
P =&\ \left\{\begin{aligned}
  S & \rightarrow A B \\
  A & \rightarrow a \\
  B & \rightarrow b \\
  C & \rightarrow c
\end{aligned}\right\}
\end{align*}

なぜならば、生成規則 $C \rightarrow c$ および非終端記号 $C$、終端記号 $c$ は、開始記号 $S$ から導出される文字列に一切寄与しないためである.
n.b. $L(G) = { ab }$

不要な記号を含まない文法について定義するとき、$N$ および $\Sigma$ の記述を省略しても差し支えない.
開始記号が明らかである場合はそれさえ省略し、$P$ と文法を同一視して次のように書くことがある.

\text{文法}\ G = \left\{\begin{align*}
  S & \rightarrow A B \\
  A & \rightarrow a A \\
  A & \rightarrow a \\
  B & \rightarrow b B \\
  B & \rightarrow b \\
\end{align*}\right\}

標準的ではないが、次の記法を用いることがある.
文法 $G = (N, \Sigma, S, P)$ に対し、$A \in N$ を用いて $G|_A = (N, \Sigma, A, P)$ とする.

適用、還元、導出、構文木

文法記号列 $\beta$、$\gamma$、および生成規則 $A \rightarrow \alpha$ があるとき、文法記号列 $\beta \ A \ \gamma$ から新たな文法記号列 $\beta \ \alpha \ \gamma$ を得ることができる.
このことを $\beta \ A \ \gamma \Rightarrow \beta \ \alpha \ \gamma$ と表し、「生成規則 $A \rightarrow \alpha$ を適用(application)することで $\beta \ A \ \gamma$ から $\beta \ \alpha \ \gamma$ を(直接-、direct -)導出(derivation)する」などと言う.

文法 $G$ が持つ生成規則を 0 回以上適用することによって $\alpha$ から $\beta$ が得られる場合は単に導出すると言い、これを $\alpha \Rightarrow^\star \beta$ のように書く.
n.b. 常に $\alpha \Rightarrow^\star \alpha$

同様に、1 回以上の適用によって $\alpha$ から $\beta$ を導出することは、$\alpha \Rightarrow^+ \beta$ のように書く.

導出の逆操作を還元(reduction)と呼び、

\begin{align*}
\beta \, A \, \gamma &\Leftarrow \beta \, \alpha \, \gamma \\
\alpha &\Leftarrow^\star \beta \\
\alpha &\Leftarrow^+ \beta \\
\end{align*}

などと書く.

開始記号 $S$ から始めて $\alpha$ を導出する過程は木構造に対応させることができ、この木を構文木(parse tree)と呼ぶ.

拡張された文法 (augmented grammar)

構文解析では、構文解析表の作成や受理条件の判定において、文の部分列と全体とを区別する必要がある、つまり、文の末尾を明示的に示さなければならない.
そこで番兵として、末尾記号 $$$ (End Of Source, EOS) を用い、上のような文法 $G$ に対して次のように定めると簡便である.

\begin{align*}
G' =& ( N \cup \{S'\}, \Sigma \cup \{\$\}, S', P \cup \{S' \rightarrow S \ \$ \}) \\
&\text{where}\ \$ \notin \Sigma \cup N
\end{align*}

明らかに、 $L(G)$ と $L(G')$ には自然な全単射が存在するから、$G$ の代わりに $G'$ を用いても一般性を損なわない.
記事中ではこのように拡張された文法 $G'$ の意味で単に $G$ と書く場合もある.

よく使う記号など

また、特に断りがない限り、各集合の元として次のような記号、またはそれらにプライムや添え字を付けたものを用いる.

\begin{align*}
A, \, B, \, C, \, \ldots &\in N \\
a, \, b, \, c, \, \ldots &\in \Sigma \\
w, \, z &\in \Sigma^\star \\
\alpha, \, \beta, \, \gamma, \, \ldots &\in (N \cup \Sigma)^\star \\
X, \, Y, \, Z &\in N \cup \Sigma
\end{align*}

共通して使用するコードなど

簡単のため、字句解析への入力は文字列に限ることとする.

各種記号

  • 非終端記号と終端記号
    util.rs
    // 記事では扱わないのだが、文法を標準形にするなどの際新しい非終端記号を定義するケースがあるので variant を持たせている
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Nonterminal<T> { pub kind: T, pub variant: usize, }
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Terminal<T> { pub kind: T }
// Symbol<T, U> としてもよいが、煩雑が過ぎるように感じたためこうしている.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum Symbol<T> {
  Nonterminal(Nonterminal<T>),
  Terminal(Terminal<T>),
}
  • トークン
    util.rs
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct TextPosition {
  pub pos: usize,// 0-indexed
  pub line: usize,// 1-indexed
  pub col: usize,// 1-indexed
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Token<T> {
  pub kind: T,
  pub start: TextPosition,
  pub end: TextPosition,
  pub value: String
}
  • 文法記号または空列
    util.rs
    // Symbol<T> に Epsilon を持たせることを嫌った形.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum NullableSymbol<T> {
  Terminal(Terminal<T>),
  Nonterminal(Nonterminal<T>),
  Epsilon
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum NullableTerminal<T> {
  Terminal(Terminal<T>),
  Epsilon
}
  • 拡張された記号
    util.rs
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum AugmentedInput<T> {
  Input(Token<T>),
  EOS
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum AugmentedSymbol<T> {
  Nonterminal(Nonterminal<T>),
  Terminal(Terminal<T>),
  EOS
}
  • 構文木の値
    util.rs
    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ParseNode<T> {
  Input(Token<T>),
  Reduction(Nonterminal<T>),
}

字句解析(参考用)

本筋ではないため、正規表現による簡単なレキサとしている.
cargo add regex でクレートを追加している(全体で利用する外部クレートはこれだけ).
もっとも、構文解析の説明ではトークン列を書き下してしまうので、lexan を使う予定はないのだが、標準的な処理の流れとしてここに記載している.

最長一致を優先し、同率一位があれば rules で先に現れるものを採用している.
空白などはスキップできるようにする実装もあるが、ここには含めていない.
また、入力として ASCII しか考慮していない点に注意.

lexer.rs
use regex::Regex;
use crate::util::{TextPosition, Token};

pub struct LexerRule<T> {
  pub kind: T,
  pub regex: Regex,
}

pub fn lexan<T: Clone + PartialEq>(
  source: &str,
  rules: &[LexerRule<T>],
) -> Vec<Token<T>> {
  let mut tokens = Vec::new();
  let mut remaining = source;
  let mut pos = 0;
  let mut line = 1;
  let mut col = 1;

  while !remaining.is_empty() {
    let mut best_match = None;
    let mut best_len = 0;

    for rule in rules {
      if let Some(mat) = rule.regex.find(remaining) {
        if mat.start() == 0 {
          let len = mat.end();
          if len > best_len {
            best_len = len;
            best_match = Some((rule.kind.clone(), mat.as_str()));
          }
        }
      }
    }// loop for rule in rules

    if let Some((kind, matched_str)) = best_match {
      let start = TextPosition { pos, line, col };

      for ch in matched_str.bytes() {// 入力は ASCII の範囲しか考慮しない
        pos += 1;
        // CR LF および LF のみを考慮し、CR 終わりの改行は考慮しない.
        if ch == b'\n' {
          line += 1;
          col = 1;
        } else {
          col += 1;
        }
      }

      let end = TextPosition { pos, line, col };

      tokens.push(Token {
        kind,
        start,
        end,
        value: matched_str.to_string(),
      });

      remaining = &remaining[best_len..];
    } else {
      panic!("Lexing error at line {line}, column {col}");
    }
  }// loop while !remaining.is_empty()

  tokens
}
テストコード
lexer.rs
#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_simple() {
    let source = "12+34*56/78-90";
    let rules = vec![
      LexerRule { kind: "num", regex: Regex::new(r"\d+").unwrap() },
      LexerRule { kind: "add", regex: Regex::new(r"\+").unwrap() },
      LexerRule { kind: "sub", regex: Regex::new(r"-").unwrap() },
      LexerRule { kind: "mul", regex: Regex::new(r"\*").unwrap() },
      LexerRule { kind: "div", regex: Regex::new(r"/").unwrap() },
    ];
    let tokens = lexan(source, &rules);
    assert_eq!(tokens.len(), 9);
    assert_eq!(tokens[0], Token {
      kind: "num",
      start: TextPosition {
        pos: 0,
        line: 1,
        col: 1,
      },
      end: TextPosition {
        pos: 2,
        line: 1,
        col: 3,
      },
      value: "12".to_string(),
    });
    assert_eq!(tokens[1], Token {
      kind: "add",
      start: TextPosition {
        pos: 2,
        line: 1,
        col: 3,
      },
      end: TextPosition {
        pos: 3,
        line: 1,
        col: 4,
      },
      value: "+".to_string(),
    });
    assert_eq!(tokens[2], Token {
      kind: "num",
      start: TextPosition {
        pos: 3,
        line: 1,
        col: 4,
      },
      end: TextPosition {
        pos: 5,
        line: 1,
        col: 6,
      },
      value: "34".to_string(),
    });
    assert_eq!(tokens[3], Token {
      kind: "mul",
      start: TextPosition {
        pos: 5,
        line: 1,
        col: 6,
      },
      end: TextPosition {
        pos: 6,
        line: 1,
        col: 7,
      },
      value: "*".to_string(),
    });
    assert_eq!(tokens[4], Token {
      kind: "num",
      start: TextPosition {
        pos: 6,
        line: 1,
        col: 7,
      },
      end: TextPosition {
        pos: 8,
        line: 1,
        col: 9,
      },
      value: "56".to_string(),
    });
    assert_eq!(tokens[5], Token {
      kind: "div",
      start: TextPosition {
        pos: 8,
        line: 1,
        col: 9,
      },
      end: TextPosition {
        pos: 9,
        line: 1,
        col: 10,
      },
      value: "/".to_string(),
    });
    assert_eq!(tokens[6], Token {
      kind: "num",
      start: TextPosition {
        pos: 9,
        line: 1,
        col: 10,
      },
      end: TextPosition {
        pos: 11,
        line: 1,
        col: 12,
      },
      value: "78".to_string(),
    });
    assert_eq!(tokens[7], Token {
      kind: "sub",
      start: TextPosition {
        pos: 11,
        line: 1,
        col: 12,
      },
      end: TextPosition {
        pos: 12,
        line: 1,
        col: 13,
      },
      value: "-".to_string(),
    });
    assert_eq!(tokens[8], Token {
      kind: "num",
      start: TextPosition {
        pos: 12,
        line: 1,
        col: 13,
      },
      end: TextPosition {
        pos: 14,
        line: 1,
        col: 15,
      },
      value: "90".to_string(),
    });
  }
}

トークン用マクロ

字句解析器の簡単な実装は示したが、構文解析器単体の説明には直接トークン列を書き下してしまう方が簡明だし適切だと考える.
トークンは位置情報なども保持する形で定義したが、誤り回復処理がなく出力するエラー情報も最小限の構文解析器では kind にしか関心がない.
そこで、kind だけでトークンのインスタンスを生成するマクロを定めることとした.

util.rs
#[macro_export]
macro_rules! tok {
  ($kind:expr) => {
    Token {
      kind: $kind,
      start: TextPosition { pos: 0, line: 1, col: 1 },
      end: TextPosition { pos: 0, line: 1, col: 1 },
      value: "".to_string(),
    }
  };
}

文法

grammar.rs
use std::hash::Hash;
use std::collections::HashSet;

use crate::util::*;

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct ProductionRule<T>
where T: Clone
{
  pub head: Nonterminal<T>,
  pub body: Vec<Symbol<T>>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CFG<T>
where T: Hash + Eq + Clone
{
  pub nonterminals: HashSet<Nonterminal<T>>,
  pub terminals: HashSet<Terminal<T>>,
  pub start: Nonterminal<T>,
  pub rules: Vec<ProductionRule<T>>,
}

impl<T> CFG<T>
where T: Hash + Eq + Clone
{
  pub fn new(start: Nonterminal<T>, rules: Vec<ProductionRule<T>>) -> Self {
    let mut nonterminals = HashSet::new();
    let mut terminals = HashSet::new();

    nonterminals.insert(start.clone());
    for rule in &rules {
      nonterminals.insert(rule.head.clone());
      for symbol in &rule.body {
        match symbol {
          Symbol::Nonterminal(nt) => { nonterminals.insert(nt.clone()); },
          Symbol::Terminal(t) => { terminals.insert(t.clone()); },
        }
      }// loop for symbol in &rule.body
    }// loop for prod in &rules

    CFG { nonterminals: nonterminals, terminals: terminals, start: start, rules: rules }
  }
}

木構造

構文木の表現に用いる. 意味解析などは扱わないため、map や fold などは含まない.
構文木としては Tree<ParseNode<T>> を想定している.

tree.rs
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Tree<T> {
  pub label: T,
  pub children: Vec<Tree<T>>,
}

impl<T> Tree<T> {
  pub fn new(label: T) -> Self {
    Self { label, children: Vec::new() }
  }
  pub fn with_children(label: T, children: Vec<Tree<T>>) -> Self {
    Tree { label, children }
  }
  pub fn append(&mut self, child: Tree<T>) -> &mut Self {
    self.children.push(child);
    self
  }
  pub fn is_leaf(&self) -> bool {
    self.children.is_empty()
  }

  pub fn show<F>(&self, stringify: F)
  where
      F: Fn(&T) -> String,
  {
    println!("{}", stringify(&self.label));
    Self::show_children(&self.children, &stringify, &mut Vec::new());
  }

  const FORK  : &'static str = "|`-- ";
  const TIP   : &'static str = "`--- ";
  const BRANCH: &'static str = "|    ";
  const BLANK : &'static str = "     ";

  fn show_children<F>(children: &[Tree<T>], stringify: &F, branches: &mut Vec<&'static str>)
  where
      F: Fn(&T) -> String,
  {
    let n = children.len();
    for (i, child) in children.iter().enumerate() {
      let is_fork = i != n - 1;
      print!("{}", branches.iter().cloned().collect::<String>());
      print!("{}", if is_fork { Self::FORK } else { Self::TIP });
      println!("{}", stringify(&child.label));

      branches.push(if is_fork { Self::BRANCH } else { Self::BLANK });
      Self::show_children(&child.children, stringify, branches);
      branches.pop();
    }
  }
}

その他定義やコード

特定の構文解析アルゴリズムでのみ使用するものについては都度定めていく.

以下のものについては、記事をまたいで参照されることとなるが、ここで定義するには煩雑であると判断した.

  • first、および follow 関数: LL(1) で定義し、SLR からも参照する.

参考文献

コンパイラ I (a.k.a. ドラゴンブック)について、私が持っているのは初版ですが、新しいもの(第二版)があるようです.

  • A.V. エイホ、R. セシイ、J.D. ウルマン 著、原田賢一 訳、『コンパイラ I ―― 原理・技法・ツール ――』、サイエンス社、1990、初版
  • J. ホップクロフト、R. モトワニ、J. ウルマン 著、野崎昭弘、高橋正子、町田元、山崎秀記 訳、『オートマトン 言語理論 計算論 I [第二版]』、サイエンス社、2003、第二版
  • その他、Wikipedia を含むネット上の情報源

  1. 専門家によるものを含め、いかなる記述であっても、その真偽は十分に吟味されるべきです. ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?