Parser preditivo ll (1) condição

Question

Vamos dizer que usamos o analisador preditivo ll (1).Por que é necessário que

$ primeiro (\ Alpha) \ cap primeiro (\ beta)=Fortyset $ ,

Para toda $ \ alfa, \ beta $ lado direito das produções alternativas, isto é, produções associadas ao mesmo não-terminal.Por que essa condição é necessária?

Answer 1

Aqui está uma explicação intuitiva:

Segue-se essencialmente da natureza de ll (1) analisadores: ll (1) analisadores construir uma tabela de parsing LL (1). As linhas da tabela são não mineral, e as colunas são terminais. Podemos pensar em ll (1) analisando como ll (1) Lookups da tabela ao encontrar cada símbolo na entrada: olhamos para a entrada determinada pelo atual nonterminal e do terminal de entrada e aplique uma regra de produção correspondente. Assim, a tabela LL (1) não pode conter várias regras de produção em cada entrada, caso contrário, o analisador não pode decidir qual regra se aplicar.

Se o lado direito de uma produção $ \ alfa $ , $ \ beta $ ter interseção Primeiros conjuntos, então teríamos várias regras em uma única entrada na tabela LL (1) (ou seja, entradas duplicadas / conflitantes) - tendo interseção não trivial de primeiros conjuntos nos impede essencialmente de construir a tabela de parsagem LL (1).

Se você ainda não está claro sobre por que esta condição é necessária , eu sugiro que você construa um exemplo com os primeiros conjuntos de interseção no lado direito de uma produção e tente construir manualmente um ll (1) tabela de parsing ou use um dos Ferramentas de visualização on-line ; Você encontrará imediatamente um conflito.