Predicate hoisting

[Andrzej Borucki]

I have read LL-star-PLDI11.pdf and predicate-hoisting.pdf

Thanks for description of algorithm. Second document, although short is more difficult and I don't quite understand some matter.

In first document is written:

"This formalism has various syntactic restrictions not present in actual ANTLR input, for example, forcing predicates to the left-edge of rules and forcing mutators into their own rules. We can make these restrictions without loss of generality because any grammar in the general form can be

translated into this more restricted form [1].”,

where [1] is ref to second document.

Whereas in second document is written:

Because our DFA construction algorithm operates on grammars that can have predicates and actions anywhere on the right-hand side, hoisting predicates into parsing decisions introduces a semantic hazard. We cannot hoist predicates over actions because they might be a function of that action.

My questions: DFA construction algorithm operates on predicates on the left-edge of rules, but in second is written “anywhere”. In second document are only samples with predicates in left edge right-hand side of production (albeit in left edge of alternative), no productions are kind of:

A->B{Pi1}?C

What is main difference of predicate hoisting extension compared to that in document 1?

How translate grammar to more restricted form?

(I want to make simplified description of this algorithm for Polish algorithm page)

Regards, Andrzej

[Terence Parr]

Hi. unfortunately I don't have time to help you with all of these questions. In general, I can point out that ANTLR sees any predicate that is not hiding from a decision point behind an action or a token.
Terence

> --
>
>

[Juancarlo Añez]

On Wed, Dec 5, 2012 at 9:42 AM, Andrzej Borucki <borucki...@gmail.com> wrote:

A->B{Pi1}?C

What is main difference of predicate hoisting extension compared to that in document 1?

How translate grammar to more restricted form?

A->B{Pi1}?C

can be translated to:

A -> B A1

A1 -> {Pi1}? C

Cheers,

--
Juancarlo Añez

tel:+58(414)901-2021
skype:juancarloanez