🦀

RustでLR(0)パーサジェネレータ

に公開
Rust
構文解析
tech

Repo

https://github.com/raiga0310/LR_parser

実行環境

以下の環境で動作を確認済み

https://github.com/raiga0310/LR_parser/blob/bfa31a66ec16a66a46b15ae6ac3dc0b4eff020d2/Cargo.toml

 rustc --version     
rustc 1.85.0 (4d91de4e4 2025-02-17)

動作例

cargo runすると動かせるが､前提として

  • group.csv: 構文解析表用CSV
  • reducer: 生成規則

が必要

group.csv

https://github.com/raiga0310/LR_parser/blob/bfa31a66ec16a66a46b15ae6ac3dc0b4eff020d2/group.csv#L1-L10

reducer

https://github.com/raiga0310/LR_parser/blob/bfa31a66ec16a66a46b15ae6ac3dc0b4eff020d2/reducer#L1-L5

実際の動作例

     Running `target\debug\LR-parser-rs.exe`
case: 1+1$
head: 1 || state: 0 || actionShift(2) || stack : [0]
head: + || state: 2 || actionReduce(5) || stack : [0, 2]
head: + || state: 4 || actionReduce(3) || stack : [0, 4]
head: + || state: 3 || actionShift(6) || stack : [0, 3]
head: 1 || state: 6 || actionShift(2) || stack : [0, 3, 6]
head: $ || state: 2 || actionReduce(5) || stack : [0, 3, 6, 2]
head: $ || state: 8 || actionReduce(2) || stack : [0, 3, 6, 8]
head: $ || state: 3 || actionAccept || stack : [0, 3]
[src\main.rs:142:5] parser.parse(String::from("1+1$")) = [
    5,
    3,
    5,
    2,
]

最後の出力が､reducerの生成規則を開始記号(ここではE)に逆順に適用することで対象のトークン列を出力できるようになっている｡
今回の入力の場合､

  • E
  • E + B 2番の E -> E + B
  • E + 1 5番の B -> 1
  • B + 1 3番の E -> B
  • 1 + 1 5番の B -> 1
    となる｡

軽い解説

LR構文解析は左からトークン列を読んで最右導出を行う｡
今回の実装では｢生成規則｣と｢構文解析表｣を構文解析する上で前提としているが､実際はLR(k)を満たす生成規則さえあればトークン列がLR構文解析でパースできるかどうか判定･ASTなどの構文木の生成が可能｡
今回は自分の構文解析への理解度を上げるためのステップを刻んだ実装で､構文解析表が正しいことを前提にパースしている｡
構文解析用の構造体Parser:

https://github.com/raiga0310/LR_parser/blob/bfa31a66ec16a66a46b15ae6ac3dc0b4eff020d2/src/main.rs#L12-L17

スタックと内部状態を持つプッシュダウンオートマトンを構文解析表tableと入力を下に動作させ､Reduce命令時に生成規則reducerを用いて還元させる｡

構文解析表をCSVから読み取ったときに､以下のように命令をenumで分類している｡

https://github.com/raiga0310/LR_parser/blob/bfa31a66ec16a66a46b15ae6ac3dc0b4eff020d2/src/main.rs#L3-L10

  • Shift(i) : 内部状態をiに遷移させ､iをスタックにプッシュする
  • Reduce(i) : i番目の規則に基づいて､右辺の文字数をスタックからポップさせる｡その後､スタックのトップを確認し､そのトップの行と還元させた非終端記号の列に対応する番号に内部状態を遷移させ､その番号をスタックにプッシュする
  • Goto(i) : Reduce命令時にi番目の内部状態に遷移させる
  • Accept : 構文解析の正常終了
  • Error : reducerを下にした文法では解析できないトークン列が渡されたときに発生､エラー

それぞれ書いた内容を実装すればよいのでそこまで難易度は高くない実装

今後の展望

調べるうちに生成規則から構文解析表の作成ができそうな気がして来たので､時間が空けばまたチャレンジしたい｡

参考

https://ja.wikipedia.org/wiki/LR法

Discussion