Por que Tomita criou o GLR e não usou Earley?

11

Quando olho para a análise de Earley, ela parece muito elegante e me pergunto por que as técnicas de GLR se tornam populares? Alguém sabe o que havia de errado com Earley analisando que Tomita criou o GLR? Atuação? Todas as publicações sobre essa discussão são muito apreciadas.

parsing Wickoo
fonte
5
O GLR permite a análise determinística em partes da gramática. Veja, por exemplo, Elkhound ( scottmcpeak.com/elkhound ), onde essa idéia é adotada. Para idiomas naturais, no entanto, não está claro que o GLR seja melhor que Earley.
24415 Sylvain
11
@Sylvain: soa como uma resposta para mim ...
Joshua Grochow

Respostas:

5

Antes tarde do que nunca.

Se bem entendi, Earley está de cima para baixo e gastará tempo e memória criando itens de Earley para cada produção em um determinado S (i). Isso significa que, para a linguagem natural, em S (0), criamos e verificamos um item de Earley para todas as palavras possíveis que iniciam uma frase, e existem muitas delas.

Mas a GLR é de baixo para cima, portanto, assumindo consultas de tabela / estado com hash eficientes, o primeiro token seleciona a (s) próxima (s) transição (ões) em tempo constante.

Isso é verdade especificamente para idiomas naturais, com o grande número de produções distintas. Mas não é realmente significativo para linguagens de programação, com o conjunto muito pequeno de produções.

Jeff
fonte