Theory

Question 1

How can we classify a regular language?

Answer 1

Language is called regular if it can be generated by a regular expression

Question 2

Every finite language is regular

True or false

Answer 2

True

Because it is the union of finitely many strings

Question 3

When does a regular expression is ambiguous?

Answer 3

A regular expression is ambiguous if the corresponding marked regular expression generates two marked strings, such that if the indices are removed, the unmark strings obtained are identical

Question 4

When a language is said to be closed?

Answer 4

A language is said to be close with respect to an operator (union, star, intersection), if the result language belongs to the same family as the operand language

Question 5

List the operators the regular language family is closed with respect to

Answer 5

Concatenation , union, and star.

Therefore, the regular languages are also closed with respect to the derived operators, cross, repetition, option, nationality, etc.

Question 6

When is a grammar considered to be in its reduced form?

Answer 6

A grammar is in reduced form if both the following conditions hold:

• Every nonterminal A is reachable from the axiom
• Every nonterminal A generates a nonempty to set of strings

Question 7

List the operators the free language family is closed with respect to

Answer 7

The family of free languages school with respect to this language operations, union, concatenation, star, and intersection.The LIB family is also closed with respect to string mirroring.

Question 8

How do we obtain the mirror grammar of a language?

Answer 8

It obtained by mirroring the right member of every rule of the former grammar

Question 9

When do we consider a grammar to be ambiguous?

Answer 9

If it admits two or more different synthetic trees (two different derivations). A grammar is said to be ambiguous if it generates at least an ambiguous string

Question 10

What are the extended free grammar?

Answer 10

Extended BNF or EBNF, are grammars in which the right side of the rules are composed by regular expressions. They closure is the same as the free language family (LIB)

Question 11

What is the method to convert an automata to a regular expression?

Answer 11

The BMC method, also known as node elimination method

Question 12

What are the automata characteristics in order to be able to apply the BMC method?

Answer 12

The initial and final states must be uniques

Question 13

How does the BMC method works?

Answer 13

It eliminate node by node adding compensation arcs to preserve the equivalence of the automata

Question 14

How can we transform a non-deterministic automaton into deterministic one

Answer 14

By eliminating the spontaneous moves and the nondeterministic multiple transitions

Question 15

What is the Berry-Sethi method (BS)?

Answer 15

It is in methods to turn a regular expression into a finite state automanton

It also can be used to determinize a non-deterministic automaton

Question 16

Can the BS algorithm be used to determinize a nondeterministic automaton with spontaneous moves?

Answer 16

Yes, it can. You just need to skip over these spontaneous transitions.

Question 17

What is the relationship between free languages and push down automata

Answer 17

The family of context-free languages coincides with that off the languages recognized by the one-state, non-deterministic push down automata

Question 18

What are the steps taken by a syntax analyzer when parsing a grammar

Answer 18

First, it reads the source string then, if the string belongs to the language, it exhibits a derivation or builds a syntax three of the string. Else it stops and notifies the error, possibly with a diagnostic

Question 19

What are the types of derivations or syntax trees formations a syntax analyzer can execute

Answer 19

A bottom up analysis which starts on the leaves and goes to the root, and a top down analysis which starts from the root and goes to the leaves

Question 20

What are the conflicts that in determines the pilot graph?

Answer 20

Shift-reduce conflict, reduce-reduce conflict, and convergence conflict

Question 21

Define the shift-reduce conflict

Answer 21

It happens when there is a reduction item with look ahead that overlaps with the terminal symbols on the outgoing arcs. This way, the push down automata is unable to choose shift or reduction.

Question 22

Define the reduce-reduce conflict

Answer 22

Two or more reduction items with look ahead that overlaps

PDA is unable to choose which reduction

Question 23

Define the convergence conflict

Answer 23

The convergence conflict occurs when there are two or more paths that merge into one state with non disjoint look ahead

Question 24

Define multiple transition in a pilot graph

Answer 24

A state has a multiple transition if it contains two or more items that their two or more next stages are defined for a single symbol (terminal or non-terminal)

A multiple transition can be convergent or not depending on the next stages of both items, if it is equal, then they are convergent

Question 25

When does a multiple transition have a conflict?

Answer 25

When it is multiple and the intersection between the look ahead groups isn’t empty

Question 26

Define the Early Parsing Algorithm

Answer 26

The algorithm starts by placing the initial state in the E[0] and calculating the closure on it. Every terminal shift maintains the pointer equal to the state that originates the new one, also it is necessary to keep calculating the closure on the new states. The nonterminal shifts are made when there are final states and they are represented as closure sets. To represent them also, you need to verify the origin of the machine you are in and the next state you are going to after completing the computation of such a machine. You also have to evaluate “j” such that it places the new state in the right group of computation denoted by the pointer.

Question 27

When does a grammar is ELL(1)?

Answer 27

When it does not have any left, most recursive derivations

When it’s pilot graph satisfies the ELR (1) conditions

When its pilot graph does not have any multiple transitions

Question 28

What are the static flow analysis used for?

Answer 28

Static flow analysis is a technique widely employed by compilers to translate high-level source programming into machine code

Question 29

When is a variable alive?

Answer 29

A variable is live at a point P, if the program control flow graph has a path from point P to another point Q and both conditions below hold

• The path does not pass through any instruction that defines the variable
• instruction Q uses the variable

Informally a variable is live at a point P, if some instruction that sooner or later can be executed starting from P uses the value, the variable happens to have point P

Question 30

What is livevness interval?

Answer 30

They are the states that are between two stages where given variables alive

Question 31

What is the flow equation method?

Answer 31

It is a method that examines the existence of some path that connects the point where the variable under examination is defined to the point where it is used

Question 32

What are the equations of the flow equation method?

Answer 32

The variables live in P are equal to the variables used in P plus the variables there are live out of P minus the ones defined in P

The variables live out of P are equal to the sum of the variables live in the successors nodes

Question 33

How can we use flow equation methods for memory location?

Answer 33

If two variables are not simultaneously live, they do not interfere and can be allocated in the same register or memory location

Question 34

When is a definition useless?

Answer 34

An instruction that defines a variable is useless if the variable is not live on at least one outgoing arc ofthe instruction

Question 35

What is the reaching definition assignment?

Answer 35

Analysis of the variable definitions, assignments that reach the points (instructions) of the program

Question 36

When does a definition of a variable reaches the input of an instruction?

Answer 36

A Definition of a variable reaches the input of an instruction if there is a path from the initial defining stage to the aimed one that do not contains another definition of that given variable

Question 37

When does a note supres variable?

Answer 37

If a note defines a variable, then every other definition of the same variable in some note, is sayed to be suppressed by P

Question 38

What are the formula of the reaching definition?

Answer 38

Variables out of P are equal to the ones defined in it, plus the ones that enter in it minus the ones that are suppressed in it

Variables that are in a P state are equal to the union of the variables that are out of the predecessors of P

Question 39

What are the types of attributes in a attribute grammar?

Answer 39

Left and right

Question 40

What are one sweep semantic evaluators?

Answer 40

Those that access each node only once

Question 41

What are the existence conditions of one sweep grammar?

Answer 41

Graph dependency is loop free

Graph dependency does not contain any pair from a left attribute to a right attribute in single node

Graph does not contain any ark from the left attribute, associated with a parent note, to any right attribute associated with child node

Brother graph is loop free as well

Question 42

How is the brother graph obtained?

Answer 42

Procedures only the right non terminals, and represents in a general overview, the dependencies of the attributes