LEXICAL ANALYSIS

 LEXICAL ANALYSIS

 1. What is Lexical Analysis?

The first phase of compiler is Lexical Analysis. This is also known as linear analysis in which the stream of characters making up the source program is read from left-to-right and grouped into tokens that are sequences of characters having a collective meaning.

2. What is a lexeme? Define a regular set.

  A Lexeme is a sequence of characters in the source program that is matched by the pattern    for a token.  A language denoted by a regular expression is said to be a regular set.

3. What is a sentinel? What is its usage?

  A Sentinel is a special character that cannot be part of the source program. Normally we use    ‘eof’ as the sentinel. This is used for speeding-up the lexical analyzer.

4.  What is a regular expression? State the rules, which define regular expression?

   Regular expression is a method to describe regular language

   Rules:

  1)   ε-is a regular expression that denotes {ε} that is the set containing the empty string

 2)  If a is a symbol in ∑,then a is a regular expression that denotes {a}

 3)       Suppose r and s are regular expressions denoting the languages L(r ) and  L(s) Then,

a)  (r )/(s) is a regular expression denoting L(r) U L(s).

b)  (r )(s) is a regular expression denoting L(r )L(s)

c)  (r )* is a regular expression denoting L(r)*.

d)  (r) is a regular expression denoting L(r ).

 

5. What are the Error-recovery actions in a lexical analyzer?

1.  Deleting an extraneous character

2.  Inserting a missing character

3.  Replacing an incorrect character by a correct character

4.  Transposing two adjacent characters

6. Construct Regular expression for the language

L= {w ε{a,b}/w ends in abb}

Ans: {a/b}*abb.

7. What is recognizer?

Recognizer are machines. These are the machines which accept the strings belonging to certain language. If the valid strings of such language are accepted by the machine then it is said that the corresponding language is accepted by that machine, otherwise it is rejected

8. Differentiate compiler and interpreter.

Compiler produces a target program whereas an interpreter performs the operations implied by the source program.

9.    Write short notes on buffer pair. 

Concerns with efficiency issues Used with a look ahead on the input It is a specialized buffering technique used to reduce the overhead required to process an input character. Buffer is divided into two N-character halves. Use two pointers. Used at times when the lexical analyzer needs to look ahead several characters beyond the lexeme for a pattern before a match is announced.

10. Differentiate tokens, patterns, lexeme.

  Tokens- Sequence of characters that have a collective meaning.

 Patterns- There is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token

 Lexeme- A sequence of characters in the source program that is matched by the pattern for a token.

 

11. List the operations on languages.

Union - L U M ={s | s is in L or s is in M} Concatenation – LM ={st|s is in L and t is in M} Kleene Closure – L* (zero or moreconcatenations of L) Positive Closure – L+ ( one or more concatenations of L)

 

12. Write a regular expression for an identifier.

An identifier is defined as a letter followed by zero or more letters or digits.The regular expression for an identifier is given as letter (letter | digit)*

 

13.  Mention the various notational shorthand's for representing regular expressions.

  One or more instances (+)

  Zero or one instance (?)

 Character classes ([abc] where a,b,c are alphabet symbols denotes the regular expressions a | b | c.)

  Non regular sets

 

14. What is the function of a hierarchical analysis?

Hierarchical analysis is one in which the tokens are grouped hierarchically into nested collections with collective meaning also termed as Parsing.

 

15. What does a semantic analysis do?

Semantic analysis is one in which certain checks are performed to ensure that components of a program fit together meaningfully. Mainly performs type checking.