The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of ∑~*a~* obey a certain periodicity property, which, in particular, makes the language {a~nb~(2~n)∣ n ≥ 0} nonrepresentable. It is also shown that {a~nb~ncs | n ≥ 0, s ∈ {a,b}} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate {a~nb~nc~* | n ≥ 0}.
展开▼
