Namaran

Code daily. Without assist.

2026-10-19

LeftRecursive.hs

type Grammar = [(Char, [String])]

leftRecursive :: Grammar -> Char -> Bool

文法(grammar)を、非終端記号とその選択肢の一覧の組を並べた Grammar で表します。大文字の英字が非終端記号(nonterminal symbol)、それ以外の文字が終端記号(terminal symbol)で、選択肢は非終端記号を置き換えてよい記号の列です。選択肢はどれも1文字以上で、1つの非終端記号の組は多くても1つしかなく、組のない非終端記号は選択肢を持ちません。非終端記号 A から始めて「いまの非終端記号の選択肢を1つ選び、その先頭の記号へ進む」ことを繰り返し、ふたたび A に着けるとき、A は左再帰(left recursive)であるといいます。終端記号に着いた道はそこで終わります。文法 g で非終端記号 a が左再帰なら True を返す leftRecursive g a を書いてください。どんな文法に対しても、有限の時間で答えを返すようにします。

入力例 1

leftRecursive [('E', ["E-n", "n"])] 'E'

出力例 1

True

入力例 2

leftRecursive [('A', ["Bx"]), ('B', ["Ay", "z"])] 'A'

出力例 2

True

入力例 3

leftRecursive [('A', ["Bx"]), ('B', ["Cy"]), ('C', ["Bz"])] 'A'

出力例 3

False
Reference
leftRecursive :: Grammar -> Char -> Bool
leftRecursive g start = go [] (firsts start)
  where
    firsts a = [c | (b, alts) <- g, b == a, c : _ <- alts]
    go _ [] = False
    go seen (c : cs)
      | c == start = True
      | c `elem` seen || not (isUpper c) = go seen cs
      | otherwise = go (c : seen) (firsts c ++ cs)

firsts a は、非終端記号 a の選択肢の先頭の記号を集めたリストで、a から1歩で進める先です。go はこれから調べる記号のリストを先頭から取り出し、start に着けば True を返します。終端記号ならその道は終わりで、非終端記号ならその先の記号をリストの前に足して調べ続けます。この進み方を深さ優先探索(depth-first search)といいます。

seen を持たずに書くと、入力例 3 で止まりません。B の先頭は C、C の先頭は B なので、start の A に着かないまま B と C を交互にたどり続けます。左再帰の文法を再帰下降構文解析でそのまま書くと止まらないのと同じ形で、どちらも先頭の記号をたどるだけで何も消費せずに同じ場所へ戻ります。一度調べた非終端記号を seen に入れて二度目は飛ばせば、非終端記号は有限個しかないので、探索は必ず終わります。入力例 2 のように別の非終端記号を経由して戻る形も、同じ探索で見つかります。

掲載したのは参考実装で、唯一の正解ではありません。Data.Char の isUpper を使っています。たどれる非終端記号の集合が増えなくなるまで広げてから、start が含まれるかを調べる書き方もできます。