Ihre Browserversion ist veraltet. Wir empfehlen, Ihren Browser auf die neueste Version zu aktualisieren.

j: FirstFollow ( r_i; NT)∩FirstFollow ( r_j; NT)= ∅〗_ " v:shapes="_x0000_s1028">A grammar is considered holding the LL(1) criteria, iff for all non_terminals NT following condition holds:

 

j: First ( r_i )∩First ( r_j )= ∅〗_ 〖∀ i=2..n: First ( r_i )∩Follow ( NT)= ∅〗_ " v:shapes="_x0000_s1026">Above rule implies, that Epsilon can be element of at most for one First ( ri ) set. Without loss of generality we will assume Epsilon will be element of First ( r1 ). Now the condition can be simplified.

 

For the extensions introduced in PILL EBNF following additional LL(1) conditions apply:

Description

Generic PILL EBNF

Additional LL(1) condition

Optional Element

NT = [ expr ] ;

  

Optional Repeat

NT = { expr } ;

  

Repeat at least 1

NT = { expr ; 1} ;

 

 

Optional List

NT = { expr1 ;  expr2 } ;

  

List at least 1

NT = { expr1 ;  expr2; 1 } ;

  

Optional Limited Repeat

NT = { expr ; 0..N } ;

Same as Optional Repeat

Limited Repeat at least 1

NT = { expr ; 1..N } ;

Same as Repeat at least 1

Optional Limited List

NT = { expr1 ;  expr2; 0..N > ;

Same as Optional List

Limited List at least 1

NT = { expr1 ;  expr2; 1..N > ;

Same as List at least 1

 

 

For the FIRST computation following rules are applied.

Context

FIRST computation

FIRST result set

Epsilon

First ( Epsilon )

{ Epsilon }

Epsilon

First ( Epsilon expr )

First ( expr )

Terminal

First ( “terminal” expr )

{ “terminal” }

Non-Terminal

NT = expr1.

NT = expr2.

First ( NT )

First ( expr1 ) + First ( expr2 )

Alternatives

First ( expr1 | expr2 )

First ( expr1 ) + First ( expr2 )

Group Element

First ( ( expr ) )

First ( expr )

Embedded Group

First ( (  expr ) expr_fol )

First ( expr expr_fol )

Embedded Optional

First ( [ expr ] expr_fol )

First ( expr expr_fol ) + First ( expr_fol )

Embedded Repeat 0

First ( { expr } expr_ fol )

First ( expr expr_fol ) + First ( expr_fol )

Embedded Repeat 1

First ( { expr ; 1 } expr_ fol )

First ( expr expr_fol )

Embedded List  0

First ( { expr1 ;  expr2 } expr_ fol )

First ( expr1 expr2 expr_fol ) + First ( expr_fol )

Embedded List 1

First ( { expr ;  expr2; 1 } expr_ fol )

First ( expr expr_fol )

Optional Element

First ( [ expr ] )

Epsilon + First ( expr )

Optional Repeat

First ( { expr } )

Epsilon + First ( expr )

Repeat at least 1

First ( { expr ; 1} )

First ( expr )

Optional List

First ( { expr1 ;  expr2 } )

Epsilon + First ( expr1 expr2)

List at least 1

First ( { expr1 ;  expr2; 1 } )

First ( expr1 expr2)

Optional Limited Repeat

First ( { expr ; 0..N } )

Epsilon + First ( expr )

Limited Repeat at least 1

First ( { expr ; 1..N } )

First ( expr )

Optional Limited List

First ( { expr1 ;  expr2; 0..N > )

Epsilon + First ( expr1 expr2)

Limited List at least 1

First ( { expr1 ;  expr2; 1..N > )

First ( expr1 expr2)