Что написать проще - парсер по алгоритму Эрли или GLL-парсер?

Если необходимо реализовать простой и быстрый парсер для конкретного контекстно-свободного языка, то лучше выбрать парсер по алгоритму Эрли. Если же вам нужно создать универсальный парсер, который может работать с любым контекстно-свободным языком, включая неоднозначные грамматики, то следует использовать GLL-парсер.

Справляется ли алгоритм Эрли с разбором текста по неоднозначной грамматике?

Алгоритм Эрли может справиться с разбором текста по неоднозначной грамматике, но это может привести к возникновению большого количества конфликтов и затруднить процесс разбора. В таких случаях лучше использовать GLL-парсер, который может обрабатывать неоднозначности и строить все возможные выводы для данной грамматики.

Является ли алгоритм Эрли алгоритмом разбора сверху-вниз?

Да, алгоритм Эрли является алгоритмом разбора сверху-вниз. Он работает с грамматикой, начиная с начального символа и пытается порождать слова, используя правила грамматики. В ходе разбора он использует стек и таблицу предсказаний, чтобы определить, какой символ следует выбирать для разбора дальше.

В каком году изобретён алгоритм Эрли?

Алгоритм Эрли был изобретен в 1970 году американским математиком Эрли, который опубликовал свою работу «An efficient context-free parsing algorithm».

Томита Масару японский профессор информатики, известный своими работами в области синтаксического анализа и компиляции. В 1984 году он предложил алгоритм GLR (Generalized LR), который может обрабатывать все контекстно-свободные грамматики, включая неоднозначные грамматики, разработал структуру данных GSS для GLR-алгоритма. Эта структура данных используется для хранения состояний разбора и управления процессом разбора.

Как расшифровывается аббревиатура GSS?

GSS расшифровывается как Graph Structured Stack.

Как расшифровывается аббревиатура GSS по-русски?

GSS расшифровывается как "стек с графовой структурой".

Стек с графовой структурой используется для хранения состояний разбора и управления процессом разбора в работе
2010, Elizabeth Scott & Adrian Johnstone, GLL Parsing

В чём же разница между алгоримами Эрли и GLL?

Разница между ними заключается в использовании разных структур данных во время разбора.

GLL-парсер использует структуру данных, которая называется Shared Packed Parse Forest (SPPF).
Он может обрабатывать неоднозначности и строить все возможные выводы для данной грамматики.

Верно ли, что алгоритм Эрли использует структуру данных GSS?
Нет, алгоритм Эрли не использует структуру данных GSS.

Лучше использовать GLL, потому что он позволяет обрабатывать больше типов грамматик. Однако если вы можете преобразовать вашу грамматику к форме, которую эффективно обрабатывает алгоритмом Эрли, то вы так же можете использовать этот метод.