صفحه 1:
Parsing
صفحه 2:
Basic Definitions
Symbol
A symbol is an entity that has no meaning by itself
Alphabet
An alphabet is a finite set of symbols.
Examples:
B= {0, 1}
C = {a, b, c}
String (Sentence)
A finite sequence of symbols from an alphabet.
Examples:
0, 1,111, 10110101
abc, cbba, bbc, aaabbbccc
English, Mary, school, John plays football.
A set of s strings from an alphabet which may be
empty, finite or infinite. A language is defined by a
grammar and we may also say that a grammer
a اح یم وه ی 7 ی نتب ای اهر
صفحه 3:
Grammar
A grammar G is defined as a four tuple (V, T, P, S),
Wwhereset of symbols called variables (S, A, B,
sae)
T is a set of symbols called terminal ( 0, 1, a, b,
gis)
S is the start variable (an element of V)
P هم وز grammer rules
An éRexple}grammer:
P:
S->aSb
S->ab
This grammer generates strings containing
an equal number of a’s and b’s starting with a’s at the
beginning of the string and b’s following the a’s. To
Generate the string aaaaabbbbb:
S => aaSbb => aaaSbbb => aaaaSbbbb =>
صفحه 4:
y, * x, VA)
Intermediate
code
sagen
Code
Generation
code
-hases of compilation
x+(y*x)
1685 /([x, +, ‘(
Parsing
syntax Analysi:
$y 7 Parsé tree
Intermediate}
Code Gen.
Object
Code
Scanning
Lexical Analysi$)~
صفحه 5:
Parsing is the task of showing whether or not a string
of symbols conforms to the syntactic rules (grammer) of
a language.
tring conforms to the rules we say that the grammar genet
ing.
A parser is a program which embodies the rules of a
While J 7 =BDo
Scanner
۳ A, > =, B, Do]
Parser ~~]
Yes, this conforms to the
syntactic rules
صفحه 6:
Parsing Expressions
Arithmetic Expressions
5
x+(y*x)
A simple grammar for expressions
expr ::= term | term
addop expr
term ::= factor | factor
multop term
factor = 'x”. | رل EST
expr rbr 13
2 ee et 3 5
۳ 1 oe T->FMT
multop POG
صفحه 7:
Representing this grammar
in Prolog ۳
We should write a relation expr, such that expr(E)
succeeds if E can be parsed as an expression. Suppose
we represent an expression as a list of symbols as
follows:
Ix, +, ‘C, y, *, x, ‘)’]
How can we parse this as an expression? The grammar
tells us that there are 2 ways that a list of symbols can
represent an expression.
The first clause i
ex
01 pple: | term addop expr
expr(E) :- term(E). % E is an expression if
itis a term
صفحه 8:
The second clause says that a list of symbols is an
expression if it starts with a term followed by an addop
and ends with an expression. So we must write code to
find the first part of the list which can be parsed as a
erm.
ee will use append(L1, L2, L3) to split the list up and
i norte af tha lict.
find all the possible first ,ره 00 ا
L=[a, b,c, d]
?- append(L1,L2,[a,b,c,d]).
Ei
£2 = [a, b; c, d] =
L1 = [a]
12 = [b, c, d];
L1 = [a, b]
L2 =[c, d];
El = [a) b; e]
L2 = [d] ;
L1 = [a, b, c, d]
L2=[];
No
صفحه 9:
Ix, +, ‘Cy, *, بل (1
append(Start, Finish, [x, +, '(', y, *,
x VD
Start = [], Finish = [x, +, (Cy,
"3,1
Start = [x], Finish = [+, '( y, *,
8
Start = [x, +], Finish = ['(', y, *,
8
Start = [x, +, '(‘], Finish = [y, *,
x
Start = [x, +, \(, y], Finish = [*,
x
Start = [x, +, '(y, *], Finish =
صفحه 10:
xpr ::= term | term addop expr
expr(L) :-
append(First, Rest, L), % Split the list
up
term(First), % find a term
at the start
append(L1, L2, Rest), %split the Rest up
addop(L1), %find an addop
expr(L2). %find an expr
صفحه 11:
rm.
term ::= factor | factor multop term
Clause 1
term(L):- factor(L).
Clause 2
term(L) :-
append(First, Rest, L), % Split the list
up
factor(First), % find a factor at the
start
append(L1, L2, Rest), %split the Rest
up
multop(L1), %find a multop
term(L2). %find a term
صفحه 12:
Factors
factor ::= ‘x’ | ‘y’ | lbr expr
rbr
A list of symbols is a factor if it is
x’ or factor([x]).
actor([y]).
factor(L) :-
append(First,
Rest, L),
lbr(First),
append(L1,
L2, Rest),
expr(L1),
rbr(L2).
صفحه 13:
Parsing operators and brackets
addop ::= ‘+’ | “'
multop ::= “*’ | ‘/’
10۲ ::< ۲
rbr ::= ‘)’
Defining operators and the brackets
addop([+]).
addop([-)).
multop([*]).
multop([-]).
Ibr(['(‘]).
rbr([')']).
صفحه 14:
we Can user expr to parse strings of symbols as expressior
x+(y*x) ۰( کب لا بط ,نک -و
Yes
Raexprly, (ax, ty, Jul): x-(x+y)
Yes
exprily, -, '(, x, +, yl). y-(xt+y ?
No
exprily./, ‘(x +, y,')')). yi(x+y) -?
Yes
?- expriLy,/, ( x, +, y,)]).
ERROR: Syntax error:
Operator expected
ERROR: expr(ly,/, (,
ERROR: ** here **
ERROR: x, +, y,)]) .
De
صفحه 15:
we have seen that we can construct a parser in Prolog
from a grammar.
It is even possible to write a Prolog program which
takes a grammar and produces a parser. Sucha
program is called a parser generators.
write a grammar directly in Prolog and use a special
predicate to parse strings.
صفحه 16:
Here is the grammar that we presented earlier
rewritten using Prolog grammer rules:
expr --> term.
expr --> term, addop, expr.
term --> factor.
term --> factor, multop, term.
factor -->[x].
factor -->[y].
factor --> lbr, expr, rbr.
addop -->['+'].
addop -->['-'].
multop -->['*'].
multop -->['/'].
Ibr -->['(‘].
rbr -->[')'].
صفحه 17:
The Prolog grammar rules are just a bunch of facts,
like any others we might have in our database. To use
them for parsing we need to give Prolog the query:
phrase(P, List)
?- phrase(expr, Ly, '*', '(', x,
۱ الل
Yes
?- phrase(factor, [y])
Yes
?- phrase(rbr, [')'])
Yes
?- phrase(factor, [y , *', x])
No
?- phrase(expr, [y, '*', x]) .
Yes
?- phrase(factor, ['(Ly, *',
x,')').
Vac
صفحه 18:
A Grammar for a very small fragment of
English
sentence --> noun _ phrase, verb_phrase.
noun_phrase --> determiner, noun.
noun_phrase --> proper_noun.
determiner -->[the].
determiner -->[a].
proper _noun -->[pedro].
noun -->[man].
noun -->[apple].
verb_phrase --> verb, noun_phrase.
verb_phrase --> verb.
verb -->[eats].
verb -->[sings].
صفحه 19:
?- phrase(sentence, [the, man, eats]).
yes
?- phrase(sentence, [the, man, eats, the, apple]).
yes
?- phrase(sentence, [the, apple, eats, a, man)).
yes
?- phrase(sentence, [pedro, sings, the, pedro]).
no
?- phrase(sentence,[eats, apple, man]).
no
?- phrase(sentence,L).
صفحه 20:
= [the, man, eats, the, man] ;
= [the, man, eats, the, apple] ;
= [the, man, eats, a, man] ;
= [the, man, eats, a, apple] ;
= [the, man, eats, pedro] ;
= [the, man, sings, the, man] ;
= [the, man, sings, the, apple] ;
= [the, man, sings, a, man] ;
= [the, man, sings, a, apple] ;
= [the, man, sings, pedro] ;
= [the, man, eats] ;
= [the, man, sings] ;
= [the, apple, eats, the, man] ;
= [the, apple, eats, the, apple] ;
= [the, apple, eats, a, man] ;
= [the, apple, eats, a, apple] ;
= [the, apple, eats, pedro] ;
= [the, apple, sings, the, man] ;
= [the, apple, sings, the, apple] ;
= [the, apple, sings, a, man] ;
ع
ع
ا
صفحه 21:
apple, sings, a, apple] ;
apple, sings, pedro] ;
man, sings, pedro] ;
man, eats] ;
man, sings] ;
apple, eats, the, man] ;
apple, eats, the, apple] ;
apple, eats, a, man] ;
apple, eats, a, apple] ;
apple, eats, pedro] ;
apple, sings, the, man] ;
apple, sings, the, apple] ;
apple, sings, a, man] ;
apple, sings, a, apple] ;
apple, sings, pedro] ;
L = [the,
[the,
L = [the,
L= [the,
[the,
L.= [the,
L = [the,
[the,
L = [the,
L = [the,
L = [the,
[the,
[the,
[the,
[the,
L = [a, apple, eats, the, man] ;
L = [a, apple, eats, the, apple] ;
L = [a, apple, eats, a, man] ;
[a, apple, eats, a, apple] ;
L = [a, apple, eats, pedro] ;
L = [a, apple, sings, the, man] ;
صفحه 22:
[a, apple, sings, the, apple] ;
[a, apple, sings, a, man] ;
[a, apple, sings, a, apple] ;
[a, apple, sings, pedro] ;
[a, apple, eats] ;
[a, apple, sings] ;
[pedro, eats, the, man] ;
[pedro, eats, the, apple] ;
[pedro, eats, a, man] ;
[pedro, eats, a, apple] ;
[pedro, eats, pedro] ;
[pedro, sings, the, man] ;
[pedro, sings, the, apple] ;
[pedro, sings, a, man] ;
[pedro, sings, a, apple] ;
[pedro, sings, pedro] ;
[pedro, eats] ;
[pedro, sings] ;
a a a a 1 ا ف-