構文解析
たとえば、インターネット上の Webページやメールアドレスをあらわす URL は、次のような構文をもっている:
http://サーバ名/パス名(webページをあらわす場合, "http://www.yahoo.com/index.html"など)
mailto:ユーザ名@ドメイン名(電子メールアドレスをあらわす場合, mailto:god@heaven.mil など)
Webブラウザに "http://ja.wikipedia.org/index.html" などの文字列を入力した場合、ブラウザはそこからサーバ名 "ja.wikipedia.org" とパス名 "index.html" を読みとらなければならない。これは構文解析の非常に簡単な例である。
一般に、形式言語の構文解析は曖昧でない言語を対象としている。ある言語が曖昧であるとは、ひとつの文にたいして2通り以上の構文解析が可能であることをいう。プログラミング言語でよく知られている例に「宙ぶらりんelse問題(dangling else problem)」がある。たとえば以下のような文脈自由文法であらわされる言語を考える:
すると、以下の文には 2通りの解釈が考えられる:
ひとつは「if A then - 」と「if B then C else D」という2つの連なった文からなるとする解釈。もうひとつは「if A then - else D」という文の中に「if B then C」という文が埋めこまれているとする解釈である。elseに対応するifがどちらかはっきりしないことからその名がある。
一般的な解決は、elseは一番近いthenと結び付くと定めて曖昧さを解消するか、エラーとする。