Skip to content
CampusPrep
AD-604 (C) · Compiler Design/Quick Revision Short Notes

Compiler Design (AD-604 (C)) - Unit 1 Short Notes

How unit 1 is examined

This unit covers what a compiler is, its structure and phases, and lexical analysis; input buffering, lexical errors and the role of the lexical analyzer carry the marks.

Introduction of Compiler, Major data Structure in compiler, types of Compiler

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A compiler is a program that translates a source program written in a high-level language into an equivalent target program in a low-level language, and reports the errors it finds in the source.</mark>

Key points.

  1. A compiler translates the whole program before execution, whereas an interpreter translates and runs one statement at a time, so compiled code runs faster but debugging is slower.
  2. The symbol table is the major data structure: it stores each identifier with its type, scope and memory address, and every phase reads or updates it.
  3. The other data structures are the token stream from the lexer, the parse or syntax tree, the intermediate code (such as three-address code) and the literal table for constants and strings.
  4. A single-pass compiler reads the source once, while a multi-pass compiler reads it several times and can therefore optimize better.
  5. A cross compiler runs on one machine but produces code for another; a just-in-time compiler translates to machine code during execution; an incremental compiler recompiles only the changed parts.
  6. Related translators are the assembler (assembly to machine code), the preprocessor, the linker and the loader.

Front-end and Back-end of compiler, Compiler structure: analysis-synthesis model of compilation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>In the analysis-synthesis model, the analysis part breaks the source program into pieces and builds an intermediate representation, and the synthesis part builds the target program from that representation.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="Source program, front end (analysis), intermediate representation, back end (synthesis), target program"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah1)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah1)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah1)"/><path class="e" d="M446,40 L535,40" marker-end="url(#ah1)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Src</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">FE</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">IR</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">BE</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">Tgt</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Source program, front end (analysis), intermediate representation, back end (synthesis), target program</figcaption></figure>

Key points.

  1. The front end (analysis) contains lexical analysis, syntax analysis, semantic analysis and intermediate code generation, and it depends only on the source language.
  2. The back end (synthesis) contains code optimization and code generation, and it depends only on the target machine.
  3. The two ends meet at the intermediate code, so m source languages and n machines need only m front ends and n back ends instead of m times n compilers.
  4. Analysis also fills the symbol table, and synthesis uses it to produce correct target code.
  5. Some books add a middle end for machine-independent optimization between the two.

various phases of a compiler

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A phase is one logical step of compilation that takes one representation of the source program and produces the next one.</mark>

Key points.

  1. The phases in order are lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization and code generation.
  2. Lexical analysis groups characters into tokens; syntax analysis builds a parse tree from the tokens using the grammar; semantic analysis checks types and declarations and produces an annotated tree.
  3. Intermediate code generation produces machine-independent code such as three-address code, for example t1 = b * c, t2 = a + t1.
  4. Code optimization improves the intermediate code in speed or space, and code generation maps it to target machine instructions and registers.
  5. The symbol table manager and the error handler are not phases but are used by every phase.
  6. For a = b + c * 5, the token stream is id = id + id * num, and the parse tree makes c * 5 a subtree because * binds tighter than +.

Lexical analysis: Input buffering, Specification & Recognition of Tokens

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>The lexical analyzer is the first phase of a compiler; it reads the source program as a stream of characters and groups them into tokens which it supplies to the parser.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Lexical analyzer (Lex) between source program (Src) and parser (Par), sharing the symbol table (Sym)"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah2)"/><path class="e" d="M229.8,46.6 Q298,72 364.3,47.3" marker-end="url(#ah2)"/><path class="e" d="M366.2,33.4 Q298,8 231.7,32.7" marker-end="url(#ah2)"/><path class="e" d="M212,61 L212,191" marker-end="url(#ah2)" marker-start="url(#ah2)"/><g class="wl"><rect x="274" y="50.5" width="47.1" height="18" rx="9"/><text class="t" x="297.5" y="59.5" dy=".35em" text-anchor="middle">token</text></g><g class="wl"><rect x="278.1" y="11.5" width="40.8" height="18" rx="9"/><text class="t" x="298.5" y="20.5" dy=".35em" text-anchor="middle">next</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Src</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Lex</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">Par</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">Sym</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Lexical analyzer (Lex) between source program (Src) and parser (Par), sharing the symbol table (Sym)</figcaption></figure>

Role of the lexical analyzer.

  1. The lexer reads the source characters and produces one token each time the parser asks for the next token, so it is the interface between the source program and the parser.
  2. It strips whitespace, tabs, newlines and comments, since the parser does not need them.
  3. It enters identifiers into the symbol table and returns a pointer to the entry along with the token.
  4. It keeps track of line numbers so that error messages can point at the right line.
  5. It pushes back the lookahead character it read one step too far, so the next token starts correctly.
  6. It reports lexical errors and recovers from them.

Token, lexeme and pattern. A token is a class of lexemes such as id, number or keyword; a lexeme is the actual character string matched by a pattern; a pattern is the rule, usually a regular expression, that describes the lexemes of a token. In count = 5; the lexeme count belongs to the token id, whose pattern is letter followed by letters or digits, and the lexeme 5 belongs to the token number.

Specification and recognition of tokens.

  1. Tokens are specified by regular expressions, for example id = letter (letter | digit)* and number = digit+.
  2. Tokens are recognized by transition diagrams, which are finite automata drawn with states and edges labelled by input characters, with a final state for each accepted token.
  3. On reaching a final state the lexer retracts the forward pointer if it read one character too many.
  4. When two patterns match, the longest lexeme wins, and a keyword is preferred over an identifier of the same spelling.

Input buffering.

  1. Reading the source one character at a time from disk is slow, and the lexer needs lookahead to know where a lexeme ends (for example to tell = from ==), so the input is read in blocks into a buffer.
  2. The two-buffer scheme uses a buffer pair of N characters each, where N is normally a disk block size such as 4096, and one system read fills a whole half.
  3. Pointer lexemeBegin marks the start of the current lexeme, and pointer forward scans ahead until a pattern matches; the lexeme is the text from lexemeBegin to forward.
  4. After a match, lexemeBegin moves to just after the lexeme and the scan continues.
  5. When forward reaches the end of one half, the other half is reloaded and forward continues into it.
  6. A sentinel is a special character eof placed at the end of each half, so that end of buffer is detected by the same test as any other character, and only when eof is seen is it checked whether the buffer end or the true end of input is reached. This saves one test per character.
[ i n t   x = 5 ; eof | y + 1 ; eof ]
  ^lexemeBegin    ^forward

Lexical errors.

  1. A lexical error is a case where no pattern matches the input, such as an illegal character like @ in an identifier, an identifier longer than allowed, a malformed number such as 12.3.4, or an unterminated string or comment.
  2. The lexer cannot find many errors alone: in fi (a == b) it sees a valid identifier fi, and the mistake is caught by a later phase.
  3. Panic mode recovery deletes successive characters from the remaining input until a well-formed token is found.
  4. Other recovery actions are to delete one extra character, insert a missing character, replace one character by another, or transpose two adjacent characters, choosing the fix that needs the fewest changes.
  5. After recovery the lexer reports the error with its line number and continues, so several errors are found in one run.

Answer frame. Input buffering plus errors (8 marks): open with the definition of input buffering and the need for lookahead; draw the buffer pair with both pointers and the sentinel; develop the six buffering points, then the lexical errors and the four recovery actions; close with the sentinel saving one test per character. Lexical analyzer (6 marks): open with the lexer as the first phase; draw the block diagram; develop the role points 1-6, then token, lexeme and pattern with the count = 5 example; close with the lexer as the interface between the source and the parser.

Pitfall: Do not say the lexeme and the token are the same; the lexeme is the string, the token is its class.

Asked: [8 marks] (May 2024) Explain input buffering with example. Discuss about lexical errors in detail. Asked: [6 marks] (May 2024) What is Lexical Analyzer? Explain role of Lexical analyzer.

Design of a Lexical Analyzer Generator, LEX

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>LEX is a tool that takes a specification of regular expressions with actions and generates a lexical analyzer program in C.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-03" viewBox="0 0 603 80" width="603" height="80" role="img" aria-label="LEX specification (lex.l) is compiled into lex.yy.c, which the C compiler turns into the lexical analyzer"><style>#dsfig-u1-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-03 .t{fill:#16181D;font-weight:500}#dsfig-u1-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-03 .dot{fill:#16181D}#dsfig-u1-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-03 .ah{fill:#454C5A}#dsfig-u1-03 .ah.hi{fill:#2340B8}#dsfig-u1-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-03 .e{stroke:#B1B7C3}html.dark #dsfig-u1-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-03 .t{fill:#E6E8ED}html.dark #dsfig-u1-03 .t.inv{fill:#0F1115}html.dark #dsfig-u1-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-03 .dot{fill:#E6E8ED}html.dark #dsfig-u1-03 .ann{fill:#8FA3FF}html.dark #dsfig-u1-03 .lbl{fill:#858D9C}html.dark #dsfig-u1-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-03 .ah{fill:#B1B7C3}html.dark #dsfig-u1-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M66,40 L191,40" marker-end="url(#ah3)"/><path class="e" d="M231,40 L363,40" marker-end="url(#ah3)"/><path class="e" d="M403,40 L535,40" marker-end="url(#ah3)"/><g class="wl"><rect x="263.7" y="31" width="68.7" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">lex.yy.c</text></g><g class="wl"><rect x="442.9" y="31" width="54.3" height="18" rx="9"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">tokens</text></g><rect class="n" x="15" y="25" width="50" height="30" rx="15"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Spec</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Lex</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">Out</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LEX specification (lex.l) is compiled into lex.yy.c, which the C compiler turns into the lexical analyzer</figcaption></figure>

Key points.

  1. A LEX program has three parts separated by %%: declarations, translation rules of the form pattern { action }, and auxiliary C functions.
  2. LEX converts the regular expressions into an NFA, combines them, converts that to a DFA, and emits the transition table used by the generated function yylex().
  3. The matched text is available in yytext and its length in yyleng.
  4. When several patterns match, the longest lexeme wins, and a tie goes to the rule listed first.
  5. The generated lexer works with a parser generator such as YACC, which calls yylex() to get each token.

Last-minute revision

  • A compiler translates a high-level source program to target code and reports errors; an interpreter runs it statement by statement.
  • Analysis (front end) depends on the source language; synthesis (back end) depends on the target machine.
  • m languages and n machines need m front ends and n back ends.
  • Phases: lexical, syntax, semantic, intermediate code, optimization, code generation.
  • The symbol table and the error handler serve every phase.
  • Token is the class, lexeme is the matched string, pattern is the rule.
  • The lexer strips whitespace and comments, fills the symbol table and returns tokens on request.
  • Buffer pair of N characters, pointers lexemeBegin and forward, and a sentinel eof saving one test.
  • Lexical error recovery: panic mode, insert, delete, replace, transpose.
  • LEX file: declarations, rules, functions; output is lex.yy.c with yylex(); longest match wins.

Memory hooks

  • Front end knows the source language, back end knows the target machine.
  • TLP: Token, Lexeme, Pattern.
  • Two buffers, two pointers, one sentinel.
  • Panic mode: delete until a token appears.
  • LEX: three parts, three percent signs in the middle, one output file.

Coverage checklist

  • Introduction of Compiler, Major data Structure in compiler, types of Compiler: no past questions.
  • Front-end and Back-end of compiler, Compiler structure: analysis-synthesis model of compilation: no past questions.
  • various phases of a compiler: no past questions.
  • Lexical analysis: Input buffering, Specification & Recognition of Tokens: May 2024 (8 marks input buffering and lexical errors; 6 marks lexical analyzer and its role).
  • Design of a Lexical Analyzer Generator, LEX: no past questions.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in