pythonで再帰下降構文解析入門 - Qiita

今回やる事 競技プログラミングをやっていたら、再帰下降構文解析を応用したようなアルゴリズムの問題がけっこう出て解けなかったので、まずは基本から理解しようと思い、自分なりにまとめてみました。 ※間違っていたらご指摘いただけると喜びます。 環境 python 3.8.5 jupyter notebook 6.2.0 構文解析とは 文字列を解析して、その文字の構成要素の意味を解析する事。 自然言語における解析と、コンパイラやプログラムなどでの使用を目的とした解析では手法が異なる。 今回は、競技プログラミングなどのプログラムおける使用を前提としているので、後者の方を追っていきます。 再帰下降構文解析とは 再帰により構文を小さな単位に分割し、解析するもので、比較的簡単に実装出来て性能はそこそこいいため競技プログラミングなどに頻出する。 処理の流れ的には、入力文字列を左から構文解析していって末尾から値