コンパイラの構成と最適化

https://gyazo.com/904bccbc87c5490afa7d72293c109b26

コンパイラの構成と最適化、数学素人の自分でも理解できるぐらい分かりやすく書いてあって、書いた人は本当に性格いい人なんだろうな、ってなってる

現在、p70 字句解析まで読了

所持済み

p51

有限オートマトン (finite automaton) とは、有限個の内部状態を持ち、与えられ また記号列を読みながら状態遷移し、その記号列がある言語の文であるかどうかを判定 する認識するといわれる)ものである。 言語の文を認識できる有限オートマトン は、Lの認識器と呼ばれる。 正規表現 Rが与えられたとき、L(R) を認識する非決定 性有限オートマトン (nondeterministic finite automaton: 以下では NFA と暗記する) は、以下の規則にしたがって生成できる。

そして非決定性有限オートマトンが生成できるということは、決定性有限オートマトンも生成できるということである

非決定性有限オートマトンから決定性有限オートマトンに変換できるアルゴリズムが存在する

ただし、後方参照と再帰を含む正規表現は、オートマトンに変換できない