如何确定某种语言是否为LL(1)？

Question

我有一个语法,我可以检查是否是LL(1).但是,有没有办法检查语法生成的语言是否为LL(1)？LL(1)语法和LL(1)语言之间究竟有什么区别？

Answer 1

任何LL(1)语法都定义LL(1)语言.根据定义,如果有一些语法生成LL(1),则语言为LL(1),因此您对该语言具有LL(1)语法的事实自动意味着该语言为LL(1) .

详细说明,语言是一组字符串,该语言的语法是描述该语言的一种手段.有些语言有LL(1)语法而有些语言没有.然而,语法不是LL(1)这一事实并不意味着它所描述的语言不是.例如,考虑这个语法:

A -> ab | ac

该语法不是LL(1),因为它在尝试在看到终端a时预测A的生产时包含FIRST/FIRST冲突.但是,它描述了LL(1)语言,因为该语言也由语法描述

A -> aX
X -> b | c

所以这些语法生成的语言(只包含ab和ac)确实是LL(1).

确定任意语法描述的语言是否是LL(1)要困难得多,据我所知,唯一的方法就是明确展示初始语法生成的语言的LL(1)语法. (这很棘手)或者在数学上证明不存在这样的语法.

希望这可以帮助!