Как понять состояние сокращения без LR(0) в практическом методе построения эффективных анализаторов LALR(k) с автоматическим восстановлением после ошибок

Question

Я не понимаю, откуда исходит состояние сокращения без LR (0). Означает ли это, что:

1. Удалите состояние уменьшения LR (0) И получите состояния LR'(0)
2. Используйте состояния LR'(0) для генерации состояний LR(K). и состояние восстановления без LR (0) происходит из состояний LR(K).

Это копия патичного метода построения эффективных паролей LALR(K) с автоматическим восстановлением ошибок.

Пожалуйста, прочитайте главу 4.2

Answer 1

Состояние сокращения - это состояние, в котором возможно уменьшение. То есть, если набор элементов состояния содержит конечный элемент, состояние является состоянием сокращения.

Если состояние сокращения равно LR(0) - что означает, что действие состояния может быть идентифицировано без какого-либо предварительного просмотра - тогда набор элементов состояния должен быть только одним элементом, который должен быть конечным. (Если бы это было не так, состояние не могло бы быть LR(0), потому что было бы доступно более одного возможного действия, которое можно различить только по прогнозу.)

Как он указывает, действие уменьшения LR (0) должно быть правильным, потому что никакое другое действие было невозможно в этом состоянии. Таким образом, даже если маркер предпросмотра сгенерирует ошибку, требующую восстановления, сокращение не нужно будет отменять. Поэтому автор предлагает убрать LR (0) редуцирующих состояний.

Конечно, не все состояния являются LR(0). В большинстве штатов предпринятые действия будут зависеть от предвидения. В частности, в состоянии сокращения без LR (0) сокращение будет зависеть от маркера предварительного просмотра. И после того, как восстановительные состояния LR (0) удалены, все оставшиеся восстановительные состояния не являются LR(0).

Но поскольку сжатие таблицы может заменить действие по ошибке сокращением по умолчанию (и, как мне кажется, из-за слияния состояний LALR, хотя вполне возможно, что в этой главе речь идет не о LALR), вполне возможно, что сокращение, указанное для токена предпросмотра на самом деле окажется неверным. В этом случае уменьшение может потребоваться отменить для восстановления после ошибки.

Предполагается, что автор полагает, что отмена сокращений, в общем, невозможна, и поэтому анализатору необходимо отложить действия сокращения (включая модификацию стека) до тех пор, пока не станет известно, что сокращения действительно действительны, что произойдет, когда анализатор в конечном итоге выполняет смену. Остальная часть главы посвящена достижению этой цели.