# 345 CS Syntax Analysis Sections 4.1-4.4: Dr. Mohamed

345 CS Syntax Analysis Sections 4.1-4.4: Dr. Mohamed Ramadan Saady CH4.1 Other Derivation Concepts Leftmost: Replace the leftmost non-terminal symbol 345 CS E E A E id A E id * E id * id lm lm lm lm Rightmost: Replace the rightmost non-terminal symbol Erm E A E rm E A id rm E * id rmid * id Important Notes: A If A , whats true about ? lm If A , whats true about ?

rm Derivations: Actions to parse input can be represented pictorially in a parse tree. CH4.2 Dr. Mohamed Ramadan Saady Examples of LM / RM Derivations E E A E | ( E ) | -E | id 345 CS A+|-|*| / | A leftmost derivation of : id + id * id A rightmost derivation of : id + id * id Dr. Mohamed Ramadan Saady CH4.3 Derivations & Parse Tree E EEAE E 345 CS A E E

E*E E A E * E id * E id * id Dr. Mohamed Ramadan Saady E A E id * E E A E id *

id CH4.4 Parse Trees and Derivations Consider the expression grammar: E E+E | E*E | (E) | -E | id 345 CS Leftmost derivations of id + id * id E E EE+E E + E + E id + E E E + E id E id + E id + E * E

Dr. Mohamed Ramadan Saady E + E id E * E CH4.5 Parse Tree & Derivations - continued E 345 CS id + E * E id + id * E E + E id E *

E id E id + id * E id + id * id E + E id E * id Dr. Mohamed Ramadan Saady E id CH4.6 Alternative Parse Tree & Derivation 345 CS EE*E E E+E*E id + E * E

E id + id * E id E * + E E id id id + id * id WHATS THE ISSUE HERE ? Two distinct leftmost derivations! Dr. Mohamed Ramadan Saady CH4.7 Resolving Grammar Problems/Difficulties Regular Expressions : Basis of Lexical Analysis 345 CS Reg. Expr. generate/represent regular languages Reg. Languages smallest, most well defined class of languages Context Free Grammars: Basis of Parsing CFGs represent context free languages

CFLs contain more powerful languages Reg. Lang. Dr. Mohamed Ramadan Saady CFLs anbn CFL thats not regular. CH4.8 Resolving Problems/Difficulties (2) 345 CS Since Reg. Lang. Context Free Lang., it is possible to go from reg. expr. to CFGs via NFA. Recall: (a | b)*abb a start a 0 1 b 2 b 3

b Dr. Mohamed Ramadan Saady CH4.9 Resolving Problems/Difficulties (3) Construct CFG as follows: 1. 345 CS 2. Each State I has non-terminal Ai : A0, A1, A2, A3 If i a j i b j then Ai a Aj then Ai bAj : A0 aA0, A0 aA1 : A0 bA0, A1 bA2 3. If

4. If I is an accepting state, Ai : A3 5. If I is a starting state, Ai is the start symbol : A0 : A2 bA3 T={a,b}, NT={A0, A1, A2, A3}, S = A0 PR ={ A0 aA0 | aA1 | bA0 ; a A1 bA2 ; start 0 a 1 A2 bA3 ; b A3 } Dr. Mohamed Ramadan Saady b 2 b 3 CH4.10 How Does This CFG Derive Strings ? a start

345 CS a 0 1 b 2 b 3 b vs. A0 aA0, A0 aA1 A0 bA0, A1 bA2 A2 bA3, A3 How is abaabb derived in each ? Dr. Mohamed Ramadan Saady CH4.11 Regular Expressions vs. CFGs 345 CS Regular expressions for lexical syntax 1. CFGs are overkill, lexical rules are quite

simple and straightforward 2. REs concise / easy to understand 3. More efficient lexical analyzer can be constructed 4. RE for lexical analysis and CFGs for parsing promotes modularity, low coupling & high cohesion. CFGs : Match tokens ( ), begin / end, if-then-else, whiles, proc/func calls, Intended for structural associations between tokens ! Are tokens in correct order ? Dr. Mohamed Ramadan Saady CH4.12 Resolving Grammar Difficulties : Motivation 345 CS The structure of a grammar affects the compiler design recall syntax-directed translation Different parsing approaches have different needs Top-Down vs. Bottom-Up redesigning a grammar may assist in producing better parsing methods. Grammar Problems Dr. Mohamed Ramadan Saady - ambiguity - -moves

- cycles - left recursion - left factoring CH4.13 Resolving Problems: Ambiguous Grammars Consider the following grammar segment: stmt if expr then stmt 345 CS | if expr then stmt else stmt | other (any other statement) Whats problem here ? Lets consider a simple parse tree: stmt if expr then stmt E1 S1 Else must match to previous then. Structure indicates parse subtree for expression. Dr. Mohamed Ramadan Saady else if stmt expr

E2 then stmt else S2 stmt S3 CH4.14 Example : What Happens with this string? If E1 then if E2 then S1 else S2 345 CS How is this parsed ? if E1 then if E2 then S1 else S2 vs. if E1 then if E2 then S1 else S2 Whats the issue here ? Dr. Mohamed Ramadan Saady

CH4.15 Parse Trees for Example Form 1: 345 CS stmt expr if then E1 stmt then expr if E2 stmt else stmt S1 S2 else stmt

Form 2: stmt if expr E1 Whats the issue here ? Dr. Mohamed Ramadan Saady then if stmt expr E2 then stmt S2 S1 CH4.16

## Recently Viewed Presentations

• We assume that orbital order is the same as that for N2. The bond order is 2.5. ... An orbital energy-level diagram for sp2 hybridization. Note that one p orbital remains unchanged. When an s and two p orbitals are...
• Youth Mental Health First Aid. Teen Self-Injury Suicide Prevention. Drugs and Vaping. Restorative Processes. Investigations, Searches and Due Process ... the CDE has resources that support the work of LEAs and make the goals of each priority attainable. Tom Torlakson....
• CORBA 3 and CORBA For Embedded Systems Dr. S. Ron Oliver U. S. Representative for Top Grap'X
• Maternal and Child Health Prevention Guidelines. Hello and welcome to our discussion on Maternal and Child Health Prevention Guidelines.
• UPPER SCHOOL UCAS Open Days EMA Easter School/Supported Study Upper School Contracts S6 Committees/School Captains/House Captains Upper School Induction Days and other events - Retreat, Work Experience Social Enterprise, Fundraising, Caritas, YASS, Lasallian/Alma, Peer Educators, Study Buddies The Importance of...
• Управляющее ПО EZStation для компьютера. Официальное программное обеспечение для настольного компьютера «EZStation»под Windows и Mac можно скачать с официального сайта компании:
• Anti-Lock Braking Systems Branden L. Jones, CSP, OHST Manager - EH&S Texas New Mexico Power Fort Worth, Texas Pop Quiz Does Anti-Lock Brake System (ABS) usage follow conventional driver training?
• Introduction to Forensic Anthropology Features of the Skull Used in Race Determination Nasal index: The ratio of the width to the height of the nose, multiplied by 100 Nasal Spine: feel the base of the nasal cavity, on either side...