Application
Note that “|” is synonymous with “U” in regular
expressions.
cs466(Prasad)
L5Appl
1
Why have different representation
formalisms for the same class of languages?
• Convenience of expression
– For certain languages, a regular grammar may
be substantially easier to write than a regular
expression (or vice versa).
– Regular expression can be mapped to a
recognizer in a language containing sequencing,
conditional, and while-loop.
– Regular grammars can be mapped to finite
automaton.
cs466(Prasad)
L5Appl
2
• Example

L  {  { a , b} |  contains
even number
and odd number
of a ' s
of b ' s}
EaEb
 a OaEb
| b EaOb
EaOb
 a OaOb
| b EaEb
OaEb
 a EaEb
| b OaOb
OaOb
 a EaOb
| b OaEb
|
RE difficult
( b * ab * a ) * b *
cs466(Prasad)
 ( a * ba * b ) * a * ba *
L5Appl
3
• Example

L  {  {a , b , c} |  does not contain abc }
RE difficult
(a | b | c) * 
 
( ( a | b | c ) * abc ( a | b | c ) * )
 
 
complement
Requires simulation of complement using union,
concatenation, and Kleene-star operation, which is not
straightforward. (Refer to: Finite State Automata results.)
cs466(Prasad)
L5Appl
4
• Closure properties
– Regular languages are closed under union,
concatenation, and Kleene-star, by definition.
However, closure under complementation and
intersection is not obvious.
• Robustness of Regular Languages
– Various formalisms (such as regular
expressions, regular grammars, and finite
automata) converge to defining the same
collection of languages.
“Intrinsic stability” of regular languages.
cs466(Prasad)
L5Appl
5
Specifying and Automatically
Generating Compiler Front-end
(Refer to: LEX,FLEX,YACC,BISON)
Lexical
Analyzer
Regular
Expressions
cs466(Prasad)
Syntax
Analyzer
Context-free
Grammar
L5Appl
Back-end
Attribute
Grammars
6
• Pattern Matching in Scripts and PLs
– E.g., Regular expressions in awk, bash, UNIX
grep, PERL, Python, Ruby, Java, .NET, etc
• Document type definition (DTD) in XML
(eXtensible Markup Language)
– Specifies context-free syntax of a webdocument using domain-specific vocabulary.
–
Document :: cs480.html
:::: Language :: HTML
:::: Meta-language :: SGML, XML
cs466(Prasad)
L5Appl
7
• Formal specification of Input and Output
formats for programs during Software
Development and Documentation.
– Helpful to the users for clarification in user
manuals.
– Helpful to the designers in order to make I/O
details explicit in a standard way.
– Helpful to the developers, the integrators, and
the testers for communication and clarification.
cs466(Prasad)
L5Appl
8
Some URLs
• LEX/YACC/FLEX/Bison:
http://dinosaur.compilertools.net/
• BNF for Java
http://cui.unige.ch/db-research/Enseignement/analyseinfo/JAVA/BNFindex.html
• XML
http://cm.bell-labs.com/cm/cs/who/wadler/xml/
cs466(Prasad)
L5Appl
9
Some URLs (Again!)
URL for opening a web-page in a Browser
– User’s concern: What is the syntax of the URL for
Google’s homepage?
• http://www.google.com/
soundness
– Programmer’s concern: What are all syntactically
legal URLs?
(The following “URLs” work in several browsers!)
•
•
•
•
•
http://yahoo.com, yahoo.com
N:\tkprasad\cs466\HW.txt
file:///N:/tkprasad/cs466/HW.txt
ftp://www.cs.wright.edu
ftp:[email protected]/
completeness
cs466(Prasad)
L5Appl
10
Ambiguity in Grammars
cs466(Prasad)
L5Appl
11
E  E E | x
Parse/derivation trees for x - x - x
E
E
E
E
E
-
-
E
-
x
x
E
x
x
E
E
E
x
x
Ambiguity:
Two parse trees for x-x-x
Two Interpretations: x, -x
cs466(Prasad)
L5Appl
12
• Using associativity information, it is possible to
rewrite the grammar.
Left associative:
E  E T | T
T  x
E  T E | T
Right associative:
T  x
• So, the language of expressions with x and – is not
inherently ambiguous.
cs466(Prasad)
L5Appl
13
Operator Associativity and Precedences :
Examples
• Right associative
• * has precedence over +
a = b = 5;
a = (b = 5);
• Left associative
cout << 5 << “abc”;
(cout << 5)<< “abc”;
cs466(Prasad)
1 + 2 * 3 = 1 + (2 * 3)
1 + 2 * 3 =/= (1 + 2)*3
• Associativity and precedence
information is typically used to
disambiguate non-fully
parenthesized expressions
containing unary prefix/postfix
operators or binary infix
operators.
L5Appl
14
Dangling Else Problem
stm
Grammar:
Ambiguity:
cs466(Prasad)

if
expr
then
stm
|
if
expr
then
stm
else
stm
if B1 then if B2 then S1 else S2
vs
if B1 then if B2 then S1 else S2
L5Appl
15
Inherently ambiguous CFL
• A context-free language that does not have
an unambiguous context-free grammar is
called an inherently ambiguous context-free
language.
L {a b c
i
cs466(Prasad)
j
k
| i  j  j  k}
L5Appl
16
S  PC | AQ
P  aPb | 
Ambiguous
Context-Free
Grammar
C  cC | 
Q  bQc | 
A  aA | 
cs466(Prasad)
L5Appl
17
Descargar

Document