プログラミング/文脈自由文法

文脈自由文法

文脈自由文法（Context-Free Grammar, CFG）は、形式言語理論における重要な概念で、プログラミング言語の構文解析やコンパイラ設計において中核的な役割を果たします。以下に、その基本概念と実装手法を詳説します。

基本定義と構成要素

文脈自由文法は、終端記号、非終端記号、生成規則、開始記号の4つの要素で構成されます。

package main

import (
    "fmt"
    "strings"
)

// 文脈自由文法の基本構造
type CFG struct {
    Terminals    []string            // 終端記号集合
    NonTerminals []string            // 非終端記号集合
    Productions  map[string][]string // 生成規則
    StartSymbol  string              // 開始記号
}

// 簡単な算術式の文法定義例
func createArithmeticGrammar() *CFG {
    return &CFG{
        Terminals:    []string{"+", "-", "*", "/", "(", ")", "id", "num"},
        NonTerminals: []string{"E", "T", "F"},
        Productions: map[string][]string{
            "E": {"E + T", "E - T", "T"},
            "T": {"T * F", "T / F", "F"},
            "F": {"( E )", "id", "num"},
        },
        StartSymbol: "E",
    }
}

// 生成規則の適用例
func (cfg *CFG) applyProduction(nonTerminal string, productionIndex int) (string, error) {
    productions, exists := cfg.Productions[nonTerminal]
    if !exists {
        return "", fmt.Errorf("非終端記号 %s が見つかりません", nonTerminal)
    }
    
    if productionIndex >= len(productions) {
        return "", fmt.Errorf("生成規則のインデックスが範囲外です")
    }
    
    return productions[productionIndex], nil
}

バッカス・ナウア記法（BNF）表現

文脈自由文法は通常BNF記法で表現され、構文解析器の設計に使用されます。

// BNF記法の表現と解析
type BNFRule struct {
    LeftSide  string   // 左辺（非終端記号）
    RightSide []string // 右辺（生成規則の選択肢）
}

type BNFGrammar struct {
    Rules []BNFRule
}

// BNF記法での文法定義例
func createBNFGrammar() *BNFGrammar {
    return &BNFGrammar{
        Rules: []BNFRule{
            {"S", []string{"A B", "C"}},
            {"A", []string{"a", "ε"}}, // εは空文字列
            {"B", []string{"b B", "b"}},
            {"C", []string{"c C", "c"}},
        },
    }
}

// BNF記法の文字列表現
func (bnf *BNFGrammar) toString() string {
    var result strings.Builder
    
    for _, rule := range bnf.Rules {
        result.WriteString(fmt.Sprintf("%s ::= ", rule.LeftSide))
        result.WriteString(strings.Join(rule.RightSide, " | "))
        result.WriteString("\n")
    }
    
    return result.String()
}

左再帰の除去

左再帰は多くの構文解析アルゴリズムで問題となるため、除去が必要です。

// 左再帰除去アルゴリズム
type LeftRecursionEliminator struct{}

func (lre *LeftRecursionEliminator) eliminateLeftRecursion(cfg *CFG) *CFG {
    newCFG := &CFG{
        Terminals:    cfg.Terminals,
        NonTerminals: make([]string, 0),
        Productions:  make(map[string][]string),
        StartSymbol:  cfg.StartSymbol,
    }
    
    // 直接左再帰の除去
    for nonTerminal, productions := range cfg.Productions {
        alpha := make([]string, 0) // 左再帰部分
        beta := make([]string, 0)  // 非左再帰部分
        
        for _, production := range productions {
            tokens := strings.Split(production, " ")
            if len(tokens) > 0 && tokens[0] == nonTerminal {
                // 左再帰の場合：A -> A α
                if len(tokens) > 1 {
                    alpha = append(alpha, strings.Join(tokens[1:], " "))
                }
            } else {
                // 非左再帰の場合：A -> β
                beta = append(beta, production)
            }
        }
        
        if len(alpha) > 0 {
            // 左再帰が存在する場合の変換
            newNonTerminal := nonTerminal + "'"
            newCFG.NonTerminals = append(newCFG.NonTerminals, nonTerminal, newNonTerminal)
            
            // A -> β A'
            newProductions := make([]string, 0)
            for _, b := range beta {
                newProductions = append(newProductions, b+" "+newNonTerminal)
            }
            newCFG.Productions[nonTerminal] = newProductions
            
            // A' -> α A' | ε
            newProductions = make([]string, 0)
            for _, a := range alpha {
                newProductions = append(newProductions, a+" "+newNonTerminal)
            }
            newProductions = append(newProductions, "ε")
            newCFG.Productions[newNonTerminal] = newProductions
        } else {
            // 左再帰がない場合はそのまま
            newCFG.NonTerminals = append(newCFG.NonTerminals, nonTerminal)
            newCFG.Productions[nonTerminal] = productions
        }
    }
    
    return newCFG
}

左因子分解

左因子分解は、複数の生成規則が同じ接頭辞を持つ場合の曖昧性を解決します。

// 左因子分解アルゴリズム
type LeftFactorizer struct{}

func (lf *LeftFactorizer) leftFactor(cfg *CFG) *CFG {
    newCFG := &CFG{
        Terminals:    cfg.Terminals,
        NonTerminals: make([]string, 0),
        Productions:  make(map[string][]string),
        StartSymbol:  cfg.StartSymbol,
    }
    
    for nonTerminal, productions := range cfg.Productions {
        factored := lf.factorProductions(nonTerminal, productions)
        
        for nt, prods := range factored {
            newCFG.NonTerminals = append(newCFG.NonTerminals, nt)
            newCFG.Productions[nt] = prods
        }
    }
    
    return newCFG
}

func (lf *LeftFactorizer) factorProductions(nonTerminal string, productions []string) map[string][]string {
    result := make(map[string][]string)
    
    // 共通接頭辞の検出
    prefixGroups := make(map[string][]string)
    
    for _, production := range productions {
        tokens := strings.Split(production, " ")
        if len(tokens) > 0 {
            prefix := tokens[0]
            prefixGroups[prefix] = append(prefixGroups[prefix], production)
        }
    }
    
    newProductions := make([]string, 0)
    counter := 0
    
    for prefix, group := range prefixGroups {
        if len(group) > 1 {
            // 左因子分解が必要
            newNonTerminal := fmt.Sprintf("%s%d", nonTerminal, counter)
            counter++
            
            newProductions = append(newProductions, prefix+" "+newNonTerminal)
            
            // 新しい非終端記号の生成規則を作成
            newRules := make([]string, 0)
            for _, production := range group {
                tokens := strings.Split(production, " ")
                if len(tokens) > 1 {
                    newRules = append(newRules, strings.Join(tokens[1:], " "))
                } else {
                    newRules = append(newRules, "ε")
                }
            }
            
            result[newNonTerminal] = newRules
        } else {
            // 左因子分解不要
            newProductions = append(newProductions, group[0])
        }
    }
    
    result[nonTerminal] = newProductions
    return result
}

LL(1) 解析表の構築

LL(1) 解析は、文脈自由文法に基づく効率的な構文解析手法です。

// LL(1) 解析表の構築
type LL1Parser struct {
    grammar      *CFG
    firstSets    map[string][]string
    followSets   map[string][]string
    parseTable   map[string]map[string]string
}

func NewLL1Parser(cfg *CFG) *LL1Parser {
    parser := &LL1Parser{
        grammar:    cfg,
        firstSets:  make(map[string][]string),
        followSets: make(map[string][]string),
        parseTable: make(map[string]map[string]string),
    }
    
    parser.computeFirstSets()
    parser.computeFollowSets()
    parser.buildParseTable()
    
    return parser
}

func (p *LL1Parser) computeFirstSets() {
    // FIRST集合の計算
    for _, nonTerminal := range p.grammar.NonTerminals {
        p.firstSets[nonTerminal] = make([]string, 0)
    }
    
    changed := true
    for changed {
        changed = false
        
        for nonTerminal, productions := range p.grammar.Productions {
            for _, production := range productions {
                tokens := strings.Split(production, " ")
                if len(tokens) > 0 {
                    firstToken := tokens[0]
                    
                    // 終端記号の場合
                    if p.isTerminal(firstToken) {
                        if !p.contains(p.firstSets[nonTerminal], firstToken) {
                            p.firstSets[nonTerminal] = append(p.firstSets[nonTerminal], firstToken)
                            changed = true
                        }
                    }
                }
            }
        }
    }
}

func (p *LL1Parser) computeFollowSets() {
    // FOLLOW集合の計算
    for _, nonTerminal := range p.grammar.NonTerminals {
        p.followSets[nonTerminal] = make([]string, 0)
    }
    
    // 開始記号にはEOFを追加
    p.followSets[p.grammar.StartSymbol] = append(p.followSets[p.grammar.StartSymbol], "$")
    
    changed := true
    for changed {
        changed = false
        
        for _, productions := range p.grammar.Productions {
            for _, production := range productions {
                tokens := strings.Split(production, " ")
                
                for i, token := range tokens {
                    if !p.isTerminal(token) {
                        // 非終端記号に対してFOLLOW集合を更新
                        if i < len(tokens)-1 {
                            nextToken := tokens[i+1]
                            if p.isTerminal(nextToken) {
                                if !p.contains(p.followSets[token], nextToken) {
                                    p.followSets[token] = append(p.followSets[token], nextToken)
                                    changed = true
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

func (p *LL1Parser) buildParseTable() {
    // 解析表の構築
    for nonTerminal := range p.grammar.Productions {
        p.parseTable[nonTerminal] = make(map[string]string)
    }
    
    for nonTerminal, productions := range p.grammar.Productions {
        for _, production := range productions {
            tokens := strings.Split(production, " ")
            if len(tokens) > 0 {
                firstToken := tokens[0]
                
                if p.isTerminal(firstToken) {
                    p.parseTable[nonTerminal][firstToken] = production
                }
            }
        }
    }
}

func (p *LL1Parser) isTerminal(symbol string) bool {
    for _, terminal := range p.grammar.Terminals {
        if terminal == symbol {
            return true
        }
    }
    return false
}

func (p *LL1Parser) contains(slice []string, item string) bool {
    for _, s := range slice {
        if s == item {
            return true
        }
    }
    return false
}

構文解析の実行

構築した解析表を使用して実際の構文解析を行います。

// 構文解析の実行
func (p *LL1Parser) parse(input []string) (bool, error) {
    stack := []string{"$", p.grammar.StartSymbol}
    inputIndex := 0
    
    for len(stack) > 1 {
        if inputIndex >= len(input) {
            return false, fmt.Errorf("入力が不足しています")
        }
        
        top := stack[len(stack)-1]
        currentInput := input[inputIndex]
        
        if p.isTerminal(top) {
            // 終端記号の場合
            if top == currentInput {
                stack = stack[:len(stack)-1] // スタックからポップ
                inputIndex++
            } else {
                return false, fmt.Errorf("期待される記号: %s, 実際の記号: %s", top, currentInput)
            }
        } else {
            // 非終端記号の場合
            if production, exists := p.parseTable[top][currentInput]; exists {
                stack = stack[:len(stack)-1] // 非終端記号をポップ
                
                if production != "ε" {
                    // 生成規則の右辺を逆順にスタックにプッシュ
                    tokens := strings.Split(production, " ")
                    for i := len(tokens) - 1; i >= 0; i-- {
                        stack = append(stack, tokens[i])
                    }
                }
            } else {
                return false, fmt.Errorf("解析表にエントリがありません: %s, %s", top, currentInput)
            }
        }
    }
    
    return inputIndex == len(input), nil
}

文脈自由文法は、プログラミング言語の構文定義から自然言語処理まで、幅広い分野で応用される重要な理論的基盤です。これらの手法を理解することで、効率的な構文解析器の設計と実装が可能になります。