From: Tracy R Reed <[EMAIL PROTECTED]>
For example, while doing some reading on parsers we run into the term
"context free grammar". What is this? So we link over to the wikipedia
article on it and find lots of complicated notation without much in the
way of explanation.
Don't feel bad about having a hard time. I took this stuff in college, yet
when I studied for the GRE a year ago, this was the area that gave me far
and away the most trouble.
http://en.wikipedia.org/wiki/Context-free_grammar
I think I've figured out what a terminal and non-terminal and
productions rules are.
Terminal production rules are rules that finish an expression. Basicly, if
you end and have reduced the entire thing using a final terminal rule,
you're done and correct. If you used a non-terminal, you need ot backup and
find another way, or the input was invalid.
But Example 1 completely loses me.
How does this grammar generate that language?
What we're told here is basicly 2 rules.
1)S->epsilon That means an empty statement (thats what epsilon is) can be
reduced to an S
2)S->aSb If you have an S surrounded by an a and a b, you can reduce that
to an S.
So valid inputs would be: empty, ab (here the S in the middle is empty),
aabb (we proved that ab is a valid S), aaabbb (we proved aabb is a valid S),
etc.Basicly, plug any of the valid values of S into #2 repeatedly, asnd you
get a^nb^n
What is that language?
Why is it not regular?
I'd love to help you here, but I'm not sure I ever understood regular.
Regular grammars are a bit easier, and may help you understand:
http://en.wikipedia.org/wiki/Regular_grammar
Basicly a grammar is regular if you always reduce going one way (left to
right or right to left).a regular language is somehow related, but my eyes
are glazing over their explanation.
I understand example 2 and example 3 although it takes some
concentration to see how all of those substitutions can work out.
Example 4 loses me again.
The stuff about derivations and syntax trees all seem pretty
straightforward.
4 is very similar to 1. Lets look at values of B first. B is the exact
same as S in #1. Valid values all follow b^nc^n
Now S is either any legal B (b^nc^n) or anything in the form aSc. The
difference between this and 1 is that S can be anything in that form, or
b^nc^n. Plug that in mentally- possible values are empty,
bc,bbcc,bbbccc,bbbbcccc,... and ac, abcc, abbccc, abbbcccc, abbbbccccc,
aabccc,aabbcccc, etc. The numbers of cs is always equal to the number of b+
the number of a. Hence a^mb^nc^(n+m).
Gabe
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
