2010年 秋期 応用情報技術者試験 問2

構文解析

宣言部と実行部からなる図1のような記述をするプログラム言語がある。その構文規則を、拡張記号で表記を拡張したBNFによって、図2のように定義した。

short  aa  ;
long   b1  ;
long   c   ;
aa  =  3  ;
b1  =  aa  -  1  ;
c   =  aa  +  2  *  b1  ;

図2において、引用符「'」と「'」で囲まれた記号や文字列、<数>、及び<識別子>は終端記号を表す。そのほかの「<」と「>」で囲まれた名前は非終端記号を表す。

<数>は1文字以上の数字の列を表し、<識別子>は英字で始まる1文字以上の英字又は数字からなる文字列を表す。

また、A | B はAとBのいずれかを選択することを表し、{A} はAを0回以上繰り返すことを表す。

<プログラム> : : = <宣言部> <実行部>
<宣言部> : : = <宣言部記述> {< ア >}
<実行部> : : = <文> {<文>}
<宣言部記述> : : = <宣言記述子> < イ > ';'
<宣言記述子> : : = 'short' | 'long'
<文> : : = <識別子> '=' <式> ';'
<式> : : = <項> {'+' <項> | '-' <項>}
<項> : : = < ウ > {'*' <因子> | '/' <因子>}
<因子> : : = <数> | <識別子>

例えば、図1の最初の行"short aa ;"は、図2の<宣言部記述>の定義に従っていて、<宣言記述子>と'short'、< イ >と'aa'、更に';'同士がそれぞれ対応していることが分かる。

[字句解析関数の定義]

プログラム記述が図2の構文規則に従っているかどうかを検査するプログラムを作成するために、字句を先頭から順番に抽出し、その種類を判定する関数gettoken()を定義する。ここでいう字句とは、構文規則における終端記号である。字句と字句は、空白や改行文字で区切られている。空白や改行文字は、字句そのものには含まれない。

字句の種類と関数gettoken()の戻り値の対応を表に示す。

なお、'short'と'long'は<識別子>には含まれない。また、いずれの終端記号にも該当しない字句やプログラム記述の終わりを検出した場合の戻り値を定義する。

[構文解析プログラム]

図3は、図2の構文規則に従って、<文>及び<式>の構文を検査するプログラムである。プログラムの前提条件を次に示す。

(1) <文>、<式>及び<項>の構文解析を行う関数をそれぞれbun()、shiki()及びkou()とする。これらの関数の戻り値は、構文が正しい場合は0、エラーが検知された場合は-1である。

(2) 構文解析を行う各関数実行開始時の変数tokenの値は、検査の対象となる文字列の最初の字句に対する関数gettoken()の戻り値である。

function bun()
    if ( token と'I'が等しい ) then
        token ← gettoken()
    else
        return -1
    endif
    if ( エ ) then
        token ← gettoken()
    else
        return -1
    endif
    if ( shiki() と -1 が等しい ) then return -1 endif
    if ( token と';'が等しい ) then
        token ← gettoken()
    else
        return -1
    endif
    return 0
endfunction

function shiki()
    if ( オ ) then return -1 endif
    while ( token と'+'が等しい 又は token と'-'が等しい )
        if ( token と'+'が等しい ) then
            token ← gettoken()
            if ( kou()と -1 が等しい ) then return -1 endif
        elseif ( token と'-'が等しい ) then
            token ← gettoken()
            if ( kou()と -1 が等しい ) then return -1 endif
        else
            return -1
        endif
    endwhile
    return 0
endfunction