左再帰性の除去

‹Name_list>, ‹Constant_list>, ‹Arithmetic_expression>, ‹Arithmetic_term> ‹Expression_list> は左再帰性の除去が必要である。 これらの左再帰性の除去を行うと以下の文法(の一例)になる。

‹Name_list>             ::= ‹Name> { "," ‹Name> }
‹Constant_list>         ::= ‹Constant> { "," ‹Constant> }
‹Arithmetic_expression> ::= ‹Arithmetic_term> {( "+" | "-" ) ‹Arithmetic_term> }
‹Arithmetic_term>       ::= ‹Arithmetic_factor> {( "*" | "/" | "%" ) ‹Arithmetic_factor> }
‹Expresion_list>        ::= ‹Expression> { "," ‹Expression> }

左括り出し

‹Name>, ‹Exp>, ‹Logical_term>, ‹Unsigned_factor> は左括り出しが必要である。これらの左括り出しを行うと以下の文法(の一例)になる。

‹Name> ::= NAME [ "=" ‹Constant>
                | "[" ( INTEGER "]"
                      | "]" "=" "{" ‹Contant_list> "}" 
                      )
                ]
‹Exp>             ::= ‹Logical_term> [ "||"  ‹Exp> ]
‹Logical_term>    ::= ‹Logical_factor> [ "&&" ‹Logical_term> ]
‹Unsigned_factor> ::= NAME [ ( "[" ‹Expression> "]" )
                           | "++" | "--"
                           ]  
                    | ( "++" | "--" ) NAME [ "[" ‹Expression> "]" ]
                    | INTEGER
                    | CHARACTER
                    | "(" ‹Expression> ")"
                    | "inputchar" 
                    | "inputint"
                    | ‹Sum_function>
                    | ‹Product_function>

First集合

各非終端記号のFirst集合を以下に示す。

First(‹Program>)              = { "main" }
First(‹Main_function>)        = { "main" }
First(‹Block>)                = { "{" }
First(‹Var_decl>)             = { "int" }
First(‹Name_list>)            = { NAME }
First(‹Name>)                 = { NAME }
First(‹Constant_list>)        = { "-", INTEGER, CHARACTER }
First(‹Constant>)             = { "-", INTEGER, CHARACTER }

First(‹Statement>)            = { "if", "while", "for", "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*",
                                         "outputchar", "outputint", "break", "{", ";" }

First(‹If_statement>)         = { "if" }
First(‹While_statement>)      = { "while" }
First(‹For_statement>)        = { "for" }
First(‹Exp_statement>)        = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Outputchar_statement>) = { "outputchar" }
First(‹Outputint_statement>)  = { "outputint" }
First(‹Break_statement>)      = { "break" }

First(‹Expression>)           = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Exp>)                  = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Logical_term>)         = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Logical_factor>)       = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Arithmetic_expression>)= { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Arithmetic_term>)      = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Arithmetic_factor>)    = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}
First(‹Unsigned_factor>)      = { NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}

First(‹Sum_function>)         = { "+" }
First(‹Product_function>)     = { "*" }
First(‹Expression_list>)      = { "-", "!", NAME, "++", "--", INTEGER, CHARACTER, "(", "inputchar", "inputint", "+", "*"}