コンパイラ

ステップ5：四則演算のできる言語の作成 まで

1.原始プログラム => 読み込み => 文字列

2.字句解析(レキシカルアナライアザ) => 符（トークン）列

字句とはプログラム上で意味のある最小の単位、(int,4587,=,+....)

3,構文解析 => 抽象構文木（abstract syntax tree）

4.中間言語作成 => 中間言語

5.最適化 => 中間言語

6.機械語出力orアセンブリを出力してアセンブル => 機械語

RISC-V

字句解析（レキシカルアナライアザ）周辺

正規文法は，文脈自由文法（CFG：Context Free Grammar）や

文脈依存文法（CSG：Context Sensitive Grammar）と比べると文を記述する能力が弱い．一般に 正規文法

は自然言語文の全体を規定（記述）するには能力不足のように言われている．本論文ではこのように役

不足と見なされている 正規文法 を精いっぱい働かせて，自然言語文を解析あるいは生成する問題を扱う．

正規文法 による文の解析や生成を行うプログラムが，有限状態オートマトン（FSA：Finite State Automaton）

である．本論文のタイトルでは，正規文法（RG）ではなく有限状態オートマトン（FSA）の方をとった．

その理由は，文の解析や生成のメカニズムやアルゴリズムに軸足を置いて議論を展開するからである．

文脈自由文法（CFG）により規定される文の処理（特に受理）を行うプログラムは，プッシュ・ダ

ウン・オートマトン（PDA：Push Down Automaton）と呼ばれる．雑に言えば，FSA に Push Down

Stack の能力を追加したオートマトンである．文の受理処理において，文構成文字列を後戻り（つまり

行きつ戻りつ）して処理できる分，能力が強化されている．

この BNF は，文脈自由文法と等価である

雑な理解

文脈自由文法 = BNF(EBNF) = プッシュダウンオートマトン

プッシュダウンオートマトンは普通のオートマトンの上位互換