07/02/12 01:34:47
>>303
その疑問はもっともだと思う。
字句解析と構文解析が別れている主な理由は、
yaccを真似たコンパイラ・コンパイラが多いことと、
字句解析には字句解析ならではの問題があるため。
他には、コンパイラの教科書でも字句解析と構文解析が分けられている
ことなんかが挙げられるかもしれない。
一般的に字句解析では、構文解析で使われるLR(k)やLALR(1)よりも
一段制約が多く、より高速に動作する正規表現という文法を使う。
普通こういうことは考えないけど、
正規表現はLALRなどのよく知られている文脈自由文法により常に表現可能で、
(逆は無理な場合がある)
原理的には字句解析を構文解析に組み込むことはできる。
ただし、現実の字句解析が教科書的で単純な方法で行われることは稀で
普通は予約語のマッチを一通り試した後、
どれにもマッチしない場合はそれを識別子として扱うという
バックトラック的な処理が必要になる。
これが普通のLALRなどではできないので、
よく知られたコンパイラ・コンパイラ、yaccやbisonなんかでは
字句解析と構文解析を一緒にやることは無理ではないかと思う。
また、速度的な観点から避けられることもある。
一昔前(yaccが作られたのは1970年代)は、
パソコンの性能が今では考えられないくらい低かったし、
理論の構築も進んでいなかったので
この二つを分けることが絶対に必要だった。
もうこの考え方は古いのかもね。