構文解析にはいろいろな手法がありますが、プログラミングコンテストでは実装が単純かつそこそこ強力な（LL(1)文法を処理できる）再帰下降構文解析がよく使われます。
これは、関数の再帰を使って構文を小さな領域に分割していき、末端から値を確定させていく手法です。
例として、四則演算の構文解析を考えます。
ここでは四則演算は数字と括弧、+-*/の4つの演算子から成り立っているとします。演算子の優先順位も実際の四則演算の通り、掛け算と割り算が優先されます。ただし、全ての演算は整数だとします。以下は式の一例です。
1+2*6/(10-7)
まずは、四則演算の構文をBNF記法で表します。 BNF記法をあまり厳格に記述する必要はありませんが、演算子の優先順位はきっちり判別できるようにしておく必要があります。
最初に、式全体をexprという変数（非終端記号）で表すとします。 exprの中から計算の優先順位を低い順にterm, factor, numberという記号を対応付けると、次のようなBNF記法を作ることができます。 （exprやtermという名前は適当に決めたものです）
<expr> ::= <term> [ ('+'|'-') <term> ]*
<term> ::= <factor> [ ('*'|'/') <factor> ]*
<factor> ::= <number> | '(' <expr> ')'
<number> :== 1つ以上の数字
このBNF表記での[...]*という表記は、括弧内のものが0回以上繰り返されることを意味します。
ICPCの問題では、BNF記法が問題文中に示されることも多いです。記法によっては繰り返しを再帰の形（例えば、<expr> ::= <term> | <term> ('+'|'-') <expr>）で表現されることもありますが、ほとんどの場合うまく変換すれば上記のような繰り返しの形に変換できます。
このBNF記法を、プログラムに落としていきましょう。
実用的な構文解析においては構文木（構文解析の結果を木構造で表したもの）を作りますが、ICPCではコーディングを簡単にするため構文木を作らずに直接値を計算することが多いです。
実際のプログラムでは、BNFで書いた構文を忠実にソースコードに落としていきます。
まずは、BNFで使用した記号と同じ名前の関数をプログラムで宣言します。
int expr(string& s, int& i);
int term(string& s, int& i);
int factor(string& s, int& i);
int number(string& s, int& i);引数は、sが今読み込んでいる式で、iが式中の位置です。参照渡しを使っているので、これらは各関数の中で共有されます。
各関数の戻り値は、構文を解析したときの値となります。戻り値は、例えば2*3をterm関数で解析したら戻り値は6となり、factor関数で解析したら乗算を処理しないため2となります。
引数と戻り値の書き方は、例えば戻り値に式のインデックスを含める（pair<int, int> expr(string& s, int i);とする）など、この他にも色々方法があるので興味のある方は調べてみてください。
次にexpr関数の中身を記述します。exprのBNF表記は<expr> ::= <term> [ ('+'|'-') <term> ]*なので、まずterm関数を呼び出してその戻り値を保持します。
その後次の文字を1つ先読みして、その文字が+か-であれば、繰り返しterm関数を呼び出して計算します。
実装した関数は次のようになります。
int expr(string& s, int& i) {
int val = term(s, i);
while(s[i] == '+' || s[i] == '-') {
char op = s[i];
i++;
int val2 = term(s, i);
if (op == '+') val += val2;
else val -= val2;
}
return val;
}同様にterm関数以下も実装していきます。こちらも1文字の先読みをしながら、BNF記法に忠実に作成していきます。
int term(string& s, int& i) {
int val = factor(s, i);
while(s[i] == '*' || s[i] == '/') {
char op = s[i];
i++;
int val2 = factor(s, i);
if (op == '*') val *= val2;
else val /= val2;
}
return val;
}
int factor(string& s, int& i) {
if (isdigit(s[i])) return number(s, i);
// ここで構文が正しければ s[i] == '(' となる
i++; // '('を読み飛ばす
int ret = expr(s, i);
i++; // ')'を読み飛ばす
return ret;
}
int number(string& s, int& i) {
int n = s[i++] - '0';
while(isdigit(s[i])) n = n*10 + s[i++] - '0';
return n;
}実際に構文解析を外から呼び出すときは、式全体を表すexpr関数に式をわたします。
int main() {
string str = "1+2*6/(10-7)";
int i = 0;
cout << str << " = " << expr(str, i) << endl; // => 5
return 0;
}これは四則演算の例を挙げましたが、これ以外の構文でもBNF記法が得られれば同様の方法で構文解析をすることができます。
上記の四則演算の構文では、1文字先読みすることで次の記号が何であるかを確定することができていました。 場合によっては、一文字先読みしただけでは次の記号が確定できないかもしれません。その場合でも、構文解析の前に字句解析を行い、構文をいくつかの意味のあるトークンに分割することで解析できるようになる場合があります。
例えば、四則演算にいくつかの数学関数を加えた文法ではsin(2)+sqrt(36)のような構文が考えられますが、sinとsqrtの2つの関数は最初の一文字では区別できません。ですが、構文を「sin」「(」「2」「)」「+」「sqrt」「(」「36」「)」のように組み分ければ、問題なく区別できます。
この項で説明したような、再帰下降＋一字句先読みで解析できる文法をLL(1)文法と言います。 しかし、再帰下降構文解析では解析できないようなより難しい文法は数多く存在します。例えば、一般の文脈自由文法はLL(1)文法よりも難しい文法です。 LL(1)文法よりも難しい文法（例えばLR(1)）の解析にはさらに複雑な構文解析をする必要がありますが、少ないコード量で記述することが難しく、そのような文法を扱う問題がICPCで出題される可能性は少ないでしょう。