構文記述BNFとは: 犬小屋は、終わらない(IT)

2025年11月17日

構文記述BNFとは

質問

構文記述BNFとはなんですか？
意味が分かりません。
複雑なBNFを書いて、javascriptのコードにしてください。

解答

1. BNFとは？

BNF (Backus–Naur Form) は、プログラミング言語やデータ構造の 文法（構文ルール）を形式的に記述する方法 です。
「この記号が出てきたら、こういう並びが許される」ということを定義します。

例（算術式のBNF）:

<expr> ::= <term> | <expr> "+" <term><term> ::= <factor> | <term> "*" <factor><factor> ::= <number> | "(" <expr> ")"<number> ::= "0" | "1" | ... | "9"

これは「足し算や掛け算を含む数式」を表す文法です。

2. 少し複雑なBNF例

簡単な MiniLang という小さな言語を考えてみます。
変数宣言、代入、四則演算、if文が書けるようにするBNFです。

<program> ::= <statement_list><statement_list> ::= <statement> | <statement_list> <statement><statement> ::= <assignment> ";" | <if_statement><assignment> ::= "let" <identifier> "=" <expr><if_statement> ::= "if" "(" <expr> ")" "{" <statement_list> "}"<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term><term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor><factor> ::= <number> | <identifier> | "(" <expr> ")"<identifier> ::= [a-zA-Z_][a-zA-Z0-9_]*<number> ::= [0-9]+

3. JavaScriptでBNFをパースする簡易コード

以下は上のBNFに沿って 再帰下降パーサー を書いた例です。
入力プログラムをAST（抽象構文木）に変換します。

// トークナイザーfunction tokenize(input) {  const tokens = [];  const regex = /\s*(=>|let|if|\(|\)|\{|\}|[0-9]+|[a-zA-Z_]\w*|==|=|\+|\-|\*|\/|;)/g;  let m;  while ((m = regex.exec(input)) !== null) {    tokens.push(m[1]);  }  return tokens;}// パーサークラスclass Parser {  constructor(tokens) {    this.tokens = tokens;    this.pos = 0;  }  peek() { return this.tokens[this.pos]; }  consume() { return this.tokens[this.pos++]; }  parseProgram() {    const statements = [];    while (this.pos < this.tokens.length) {      statements.push(this.parseStatement());    }    return { type: "Program", body: statements };  }  parseStatement() {    if (this.peek() === "let") return this.parseAssignment();    if (this.peek() === "if") return this.parseIf();    throw new Error("Unexpected token: " + this.peek());  }  parseAssignment() {    this.consume(); // let    const id = this.consume();    this.consume(); // =    const expr = this.parseExpr();    this.consume(); // ;    return { type: "Assignment", id, expr };  }  parseIf() {    this.consume(); // if    this.consume(); // (    const cond = this.parseExpr();    this.consume(); // )    this.consume(); // {    const body = [];    while (this.peek() !== "}") {      body.push(this.parseStatement());    }    this.consume(); // }    return { type: "If", cond, body };  }  parseExpr() {    let node = this.parseTerm();    while (this.peek() === "+" || this.peek() === "-") {      const op = this.consume();      const right = this.parseTerm();      node = { type: "BinaryExpr", op, left: node, right };    }    return node;  }  parseTerm() {    let node = this.parseFactor();    while (this.peek() === "*" || this.peek() === "/") {      const op = this.consume();      const right = this.parseFactor();      node = { type: "BinaryExpr", op, left: node, right };    }    return node;  }  parseFactor() {    if (/^[0-9]+$/.test(this.peek())) {      return { type: "Number", value: parseInt(this.consume(), 10) };    } else if (/^[a-zA-Z_]\w*$/.test(this.peek())) {      return { type: "Identifier", name: this.consume() };    } else if (this.peek() === "(") {      this.consume();      const expr = this.parseExpr();      this.consume(); // )      return expr;    }    throw new Error("Unexpected factor: " + this.peek());  }}// 使用例const code = `  let x = 5 + 3 * 2;  if (x) {    let y = x - 1;  }`;const tokens = tokenize(code);const parser = new Parser(tokens);const ast = parser.parseProgram();console.log(JSON.stringify(ast, null, 2));

4. 実行するとどうなるか

上記コードを実行すると、次のようなAST（抽象構文木）が得られます:

{  "type": "Program",  "body": [    {      "type": "Assignment",      "id": "x",      "expr": {        "type": "BinaryExpr",        "op": "+",        "left": { "type": "Number", "value": 5 },        "right": {          "type": "BinaryExpr",          "op": "*",          "left": { "type": "Number", "value": 3 },          "right": { "type": "Number", "value": 2 }        }      }    },    {      "type": "If",      "cond": { "type": "Identifier", "name": "x" },      "body": [        {          "type": "Assignment",          "id": "y",          "expr": {            "type": "BinaryExpr",            "op": "-",            "left": { "type": "Identifier", "name": "x" },            "right": { "type": "Number", "value": 1 }          }        }      ]    }  ]}

BNFはつまり「文法の設計図」、上のJavaScriptコードは「その設計図をもとに構文を解析する仕組み」です。