The man has a dog
Sentential forms
All the sentential forms containing NO non-terminal symbols which can be produced from S will be the legal sentences obtainable in this language.
A formal grammar that is able to generate all valid
strings in a language is also known as a generative grammar.
20
19 20
We already observe that there are many different orders in which the rules can be used to produce the sentence and this could mean trouble when we want to decide if a sentence is legal or not. Why?
Which order should you use? Does it matter?
Yes – You get ambiguous interpretation: I saw the lady with the binoculars
21
a. I saw the lady with the binoculars S
NP VP
V NP
NP PP
I saw the lady with the binoculars
I saw [the lady with the binoculars]
21 22
b. I saw the lady with the binoculars S
NP VP
VP PP
I saw the lady with the binoculars
I [ saw the lady ] with the binoculars
Lessons about grammar from NLs
1. The rules help us to generate a sentence and how to combine the words in a sentence
2. The interpretation that follows depends on word meanings
3. The interpretation could be ambiguous
4. The interpretation could still make sense even if it is ungrammatical
24
23 24
4
8/14/21
What about grammar for PLs
1. The rules help us to generate a sentence and how to combine the words in a sentence
2. The interpretation that follows depends on word meanings
3. The interpretation could be ambiguous
4. The interpretation could still make sense even if it is ungrammatical
25
What about grammar for PLs
3. The interpretation could be ambiguous
While the above is true, we have to make sure that our grammar for the PL is itself unambiguous!!
Does anyone know of a classic example?
26
25 26
The Dangling Else Problem – ALGOL 60
If a then b
If a then b else c
Simple rules for “if then else” statement, right?
But, what about: Ifathenifbthenc elsed
Where should “else” be attached to?
27
Possible Solutions
Disallowed “if” to follow “then”
Use brackets to clearly identify the pairing
The two forms are expressed differently: ifadob vs ifathenbelsec
28
27 28
29 30
What about grammar for PLs
2. The interpretation that follows depends on word meanings
If so, how do the statements of a PL get interpreted?
You need a “Turing Machine” or some appropriate underlying machinery
That is, you can’t just write a grammar, but one supported by a suitable machine.
29
Desiderata for the design of a PL
An unambiguous grammar
An effective implementation of it
An underlying machinery powerful enough to support it
30
5
8/14/21
Unlike natural language, the grammar of a PL is needed only to decide if an input string is a legal sentence or not. Why?
To do so, we use the grammar rules to group the input symbols until they reduce to S. What can we say about this process itself?
On Parsing a Programming Language
Note that the general form of productions allowed is:
xày
where both x and y represent sentential forms
32
31 32
33 34
Recall that a sentential form is all the intermediate stages while parsing a sentence
The The man
The man has a The man has a dog
Sentential forms (all the intermediate stages while parsing a sentence)
All the sentential forms containing NO non-terminal symbols which can be produced from S will be the legal sentences obtainable in this language.
33
By restricting what could be on the left and right side of the production, Chomsky discovered four interesting types of grammar
Type0: xày Type1: xAyàx*y Type2: Aà*
Type3: Aàa AàaB
x and y represent sentential forms
A, B represent non-terminals, * means anything,
a means terminal
What can you tell me about this classification?
34
Chomsky Classification
Type 0: xày Type1: xAyàx*y
Type2: Aà* Type 3: Aàa
No restrictions
A non-terminal can only be reduced in the context of x and y
A non-terminal can be reduced anytime!
A non-terminal can only be AàaB reduced in a restricted way
35
Chomsky Classification
Type 0:
Type 1:
Type 2:
xày
xAy à x*y Aà*
unrestricted context sensitive context free regular
Type3: Aàa AàaB
Note that the above does not mean that all the rules of a given language must be of a single type!
36
35 36
6
8/14/21
Chomsky Classification
Type 0: xày There is also a hierarchy
Type1: xAyàx*y
Type2: Aà*
Type3: Aàa AàaB
of types:
0⊇1⊇2⊇3
a ⊇ b meaning a properly includes b (a is a superset of b), i.e. b is a proper subset of a or b is in a
Which type is most powerful?
37
How does Chomsky classification help us in designing grammars for PLs?
Recall that for PLs our goal is to decide if the input is a legal sentence.
If so, we ask which type of grammar is needed for PLs and why.
Note that the simpler the type, the easier it is to implement but will it be powerful enough?
38
37 38
Type 3: Aàa or AàaB Type 3 grammar is also referred to as a
right-linear or left-linear grammar.
A linear grammar is one with at most one non-terminal at the r.h.s of a production.
Do you now see why we call it a linear
grammar? Always expand one rule at a time
39
Examples of Linear Grammars
SàaSb SàabS Sà ̀ε Sàa AàAab | B
Bàa
ab a aab
aabb aaabbb {anbn :n≥0}
aba ababa abababa
{a(ba)n : n ≥ 0}
aabab
aababab {a(ab)n :n≥1}
40
39 40
So, which is a right-linear grammar?
SàaSb Sàε
Neither or a mix
SàabS Sàa
Right-linear
Sà ̀Aab | B Bàa
Left-linear
41
Right linear vs Left linear
SàabS Sàa
Replace right a with aba
Sà ̀Aab | B
a
aba ababa abababa
B à a aab
aabab aababab
{a(ab)n :n≥1}
Replace left a with aab
42
{a(ba)n :n≥0}
41 42
7
8/14/21
We talked about a Type 3 grammar: Type 3: Aàa or AàaB
We can now define it as one which is any right-linear grammar or left-linear grammar.
43
Which is not a regular grammar?
S àX a S b
Sà Linear but
not regular
S à a b S Sàa
Linear and regular
S à A a b AàAab | B Bàa
Linear and regular
ε
44
43 44
A grammar for defining numbers. What kind of a grammar is this? regular
numberàinteger | real
integer à digit+
realàinteger exponent | decimal (exponent | ε ) decimalàdigit* (. digit | digit .) digit* exponentà(e | E) (+ | – | ε ) integer
digità0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
* Means 0 or more repetition and a + means 1 or more repetition.
45
A grammar for defining numbers. What kind of a grammar is this?
numberàinteger | real SàA | B integer à digit+ A à digit+
realàinteger exponent | decimal (exponent | ε ) BàA exponent | d ( exponent | ε )
decimalàdigit* (. digit | digit .) digit* exponentà(e | E) (+ | – | ε ) integer digità0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
These 3 rules expand to terminals only
46
45 46
Turing machines are most powerful
and general, why? Because it could compute
any computable function.
With restricted grammars, what machine is needed to decide if the input is a legal sentence of that grammar?
47
Type 3: Aàa or AàaB Type 3 grammar is the simplest – why
Because you are always reducing to a single non-terminal using a terminal or a terminal follows by a non-terminal.
So, if you are going to reduce one
state at a time, what kind of a
machine do you use? A finite state machine
48
47 48
8
8/14/21
Example: A deterministic FSM for password:
apy8
H
S0 S1 S2 S3 S4 S5 ≠a≠p≠y≠8
≠H
S6
49
Example: A nondeterministic FSM
Sàa* | (ab)*. S1 a
a
S0
a
What is the difference between a deterministic and a nondeterministic FSM?
; () is not part of the syntax
a
S2 b S3
50
49 50
So, is a regular grammar good for defining programming languages?
No, it is not powerful enough because it lacks recursion (or recursive definition)
But, it can be implemented in a very efficient way.
51
Recall this grammar:
Sà ̀Aab | B Bàa
Is this a regular grammar? Left- or right-linear?
Is it recursive? Looks like it!
But, did I not say that a regular grammar is not powerful enough because it lacks recursion?
52
51 52
What does recursion mean in languages?
It is not tacking on additional clauses ad infinitum or repeat a sound over and over again.
That is what that rule does: AàAab
It is about allowing the use of embedded
structure [a sentence within a sentence]
53
The best example is center-embedding:
[The cat] [likes fish] ab
[The cat] the dog chased [likes fish] aabb
This is because you can’t tell if the sentence is embedded or tacked on.
54
53 54
9
8/14/21
In other words, a recursive definition is one that allows you to call S itself:
For sentences, you want embedded sentences: S
The cat the dog chased likes fish S
For functions, you want embedded functions:
Fact (x) = x * fact (x-1)
55
• •
Type 2: Aà*
A single nonterminal on the l.h.s
A string of terminals and nonterminals on the r.h.s
Observe that we now relax the r.h.s. Implications? This type allows recursive definition
but why?
Because you can specify anything on the right and so you could have an embedded sentence there (i.e. call S again)!
56
55 56
• •
Type 2: Aà*
A single nonterminal on the l.h.s
A string of terminals and nonterminals on the r.h.s
Type 2 is thus more powerful than type 3.
Type 2 is known as a context-free grammar
but why? Replacing a non-terminal, A, does not depend on what is around it!
57
Type 2: Aà*
So what kind of a machine is needed to decide a
context-free grammar?
Observe that the r.h.s could still be as simple as a regular grammar rule and we are still reducing to a single terminal at a time.
Consequently, we could use a FSA (or FSM). But, how do we deal with embedded structure?
58
57 58
59 60
Type 2: Aà*
The answer is use a pushdown automata
(PDA i.e. implemented using a stack).
Graphically:
FSM
return
FSM return call
call FSM
Use an FSM to decide and whenever you have an embedded structure, call another FSM.
59
Type 2: Aà*
A part of a context-free grammar is regular
iff it is not self-embedding. Implications?
As we have already observed, that means we could use an FSM to parse that part of the grammar. This is good because using an FSM is fast and efficient.
Most programming languages are defined by a context-free grammar
60
10
8/14/21
Our earlier example of the part of a typical PL grammar defining ”number”. Look, no self-embedding definition (i.e. number does not appear on the rhs of any rules!
numberàinteger | real
integer à digit+
realàinteger exponent | decimal (exponent | ε ) decimalàdigit* (. digit | digit .) digit* exponentà(e | E) (+ | – | ε ) integer
digità0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
* Means 0 or more repetition and a + means 1 or more repetition.
61
Type 1: xAyàx*y
• xandymaybeempty
• A is a single nonterminal
• * is a non empty string of
nonterminals and terminals
This type is known as a context-sensitive grammar. Why?
Again, what machine is needed to decide such a language?
62
61 62
Type 1: xAyàx*y First, observe that to identify A, we need
to look at more than what A is!
This rules out the use of a state machine
You need the power of a Turing machine. However, observe that the string never increases in length when reducing it. Why?
Consequently, what you need is a linear bounded automata (i.e. a TM with restricted tape)
63
Linear bounded automata
Input string
[abcde] Working space
Left-end marker
in tape
Right-end marker
State table
Computation is done between end markers. So called because the number of accessible cells is a linear function of the input-size.
64
63 64
Type 0: xày • Unrestricted
It generates the recursively enumerable languages and can be recognized by Turing machines.
If so, every computable function can have its syntax defined by Type 0 grammar.
However, it is too general for computer language although still unable to cope with the English language
65
Conclusion
Not only that we have different grammars but they are also supported by different automata, reflecting their power.
Understanding them will help us in designing grammars for programming languages and knowing their limitations.
66
65 66
11