epsilon terminal?

[Mark Chen]

Is epsilon a terminal or a non-terminal?

Also, what is the exact definition of an LL1 grammar?

Thanks

[Philip]

As far as I know, neight, it's just eplison.

[Prabhakar Ragde]

Mark Chen <m8c...@rees.math.uwaterloo.ca> writes:

> Is epsilon a terminal or a non-terminal?

It isn't really either. It's a way of getting rid of a nonterminal
symbol without replacing it by a terminal symbol.

> Also, what is the exact definition of an LL1 grammar?

Do you really want to know?

http://www.cs.nott.ac.uk/~txa/g51mal.2001/notes/node36.html

I doubt that this is necessary knowledge for 241, but Troy is the
final arbiter. You may be able to make do with the intuitive idea that
an LL(1) grammar is one from which you can construct a
recursive-descent or top-down parser. --PR

--
Prabhakar Ragde plr...@uwaterloo.ca
Professor, School of Computer Science DC 1314, (519)888-4567,x4660
Faculty of Mathematics Waterloo, Ontario CANADA N2L 3G1
University of Waterloo http://db.uwaterloo.ca/~plragde

[Mark Chen]

In attemping to find out whether a given context-free language is LL(1),
is it sufficient to say that it is LL(1) if it meets the following
condition:

Given any of its non-terminals, the production rules with that
non-terminal on the left-hand side never yield the same terminal as the
left-most symbol of the right-hand side more than once.

And does this also apply to epsilon? Is the grammar ambiguous if you can
find more than one way to get epsilon? Like, if there is a non-terminal
<N> which turns to epsilon or <C>, and <C> turns to epsilon. Then there
can be two different trees to get epsilon.

[Prabhakar Ragde]

Mark Chen <m8c...@rees.math.uwaterloo.ca> writes:

> In attemping to find out whether a given context-free language is LL(1),
> is it sufficient to say that it is LL(1) if it meets the following
> condition:
>
> Given any of its non-terminals, the production rules with that
> non-terminal on the left-hand side never yield the same terminal as the
> left-most symbol of the right-hand side more than once.

If a grammar violates this condition, and the non-terminal appears in
some derivation, then it is not LL(1). So it is necessary. I don't
think it's sufficient, but I don't really have time today to try to
construct a counterexample. My thinking is that if this were a
complete characterization, it would be simpler than the one to which I
pointed you, and they wouldn't have given the more complicated definition.

> And does this also apply to epsilon? Is the grammar ambiguous if you can
> find more than one way to get epsilon? Like, if there is a non-terminal
> <N> which turns to epsilon or <C>, and <C> turns to epsilon. Then there
> can be two different trees to get epsilon.

Ambiguity is defined in terms of complete parse trees. So you also
need to have this nonterminal be reachable (that is, it occurs in some
complete parse tree). Then you have ambiguity. In this case, your
condition is sufficient for ambiguity, but it is not necessary. --PR

[Matei]

Epsilon is neither a terminal nor a non-terminal. It's a way of denoting
that a non-terminal can be expanded to an empty sequence of symbols. In
general, a rule in a CFG is of the form X -> Y_1 Y_2 Y_3 ... Y_n where
Y_1..n are symbols. Epsilon is written to indicate that n is 0.