3-2 Language Processor

Highlighted text? Practice this concept. Highlighted passages and figures open related questions.

Practice related questions (3)Progress & bookmarks

Current section

p. 217

Practice this section 3 linked exam questions with default filters

Progress

Not marked complete

3 - 2 Language Processor

A language processor is software that translates programs that are written in a programming language (other than machine language) into a machine language or an intermediate language (a language between a machine language and a high-level language). Even though the program before translation and the program after translation can process the same work, their content differs and they are distinguished as described below.

Original textbook callout or table. Source text: • Source program This is a program that is written in a programming language other than machine language. • Object program This is a program that has been translated into machine language or an intermediate language. — p. 217 · Enlarge

p. 218

3-2-1 Types of Language Processors

(1) Assembler

An assembler is a language processor that translates a source program written in an assembly language into an object program. Translating with an assembler is called “assembling.”

(2) Compiler

A compiler is a language processor that translates a source program written in a high-level language into an object program. Translating with a compiler is called “compiling.” A high-level language that is translated by a compiler is called a compiler language. Typical examples include COBOL and C. Since instructions of high-level languages are translated into multiple machine languages, a dedicated compiler for each language is required.

Original textbook callout or table. Source text: [Translation procedure of a compiler] (1) Lexical analysis This divides a source program which is a sequence of character strings in units of tokens. (2) Syntax analysis This analyzes the character strings according to the grammar of the programming language, and generates a syntax tree. (3) Semantic analysis This analyzes the meaning of a syntax tree and generates an intermediate code. (4) Optimization In order to increase processing efficiency upon execution and reduce execution time, this simplifies expressions in the intermediate code and modifies the structure. (5) Code generation This converts the intermediate code into an object code of the machine language (or an intermediate language). — p. 218 · Enlarge

(1) Lexical analysis A general programming language is defined with formal language based on context-free grammar. Therefore, the program is divided into units of character strings (i.e., tokens) with finite automaton or other method which is used to interpret regular expressions. In general programming languages, identifiers, constants, keywords,

p. 219

operators, and such other elements are divided as tokens.

Original formal-language and regular-expression definitions, including [A-Z]*[0-9]+ and its literal explanation. State-transition table columns S0, S1, S2: alphabetic A-Z goes to S0,S2,S2; number 0-9 goes to S1,S1,S2. S0 is initial, S1 accepting. Diagram continues on the next page. Source text: • Context-free grammar This is a grammar that enables symbols to be replaced without relying on the preceding or subsequent context. For example, with context-free grammar, if “A” is defined as “xy” or “yz”, “xyz” can be replaced by either “Az” or “xA”. • Formal languages These are languages, such as programming languages, for which a strict grammar is defined. In contrast, the language that is used in everyday conversation is sometimes called natural language. • Regular expression This is a notation method that is used in the definition of a string format (i.e., pattern). [Example of notation in regular expression] [A-Z]*[0-9]+ [A-Z]: Represents a single alphabetical character [0-9]: Represents a single number *: Represents the repetition of zero or more times of the immediately preceding regular expression +: Represents the repetition of one or more times of the immediately preceding regular expression Note: In the strings defined in this example, after an alphabetical character is repeated zero or more times, a number is repeated one or more time. In other words, “AB1” and “123” are applicable, but “ABC” and “12A” are not applicable. • Finite automaton An automaton is a notation method that models the difference in processing of input depending on the internal state. A finite automaton is composed of a finite number of states and transitions, and is represented with a state transition table, a state transition diagram, or such other method. [Representation with a state transition table] S0 S1 S2 Alphabetical character (A - Z) S0 S2 S2 S0: Initial state Number (0 - 9) S1 S1 S2 S1: Accepting state [Representation with a state transition diagram] — p. 219 · Enlarge

Finite automata: input and internal state · 1 practice questions

p. 220

State-transition diagram: initial arrow to S0; alphabetic-character loop on S0; number arrow S0 to double-circled accepting S1; number loop on S1; alphabetic-character arrow S1 to S2; alphabetic-character or number loop on S2. Source text: — p. 220 · Enlarge

Finite automaton transition diagram · 1 practice questions

(2) Syntax analysis This interprets the token structure according to the grammar of the programming language, and generates a syntax tree. In context-free grammar, syntax is often defined with BNF notation or a syntax diagram, so this can be called an activity to confirm that the tokens in the program constitute the correct meaning.

Original BNF grammar, complete aligned derivation of +4-12*6, and syntax-diagram definition. All original operators, production symbols, underlines, alternatives, colors and derivation steps are preserved in the crop. Source text: • BNF (Backus Naur Form) notation This is a metalanguage (i.e., a language to define a language) that defines the grammar of a programming language or such other aspects. It is also used for the definition of XML, and so on. [Example of BNF notation] <expression> ::= <numeric value>|<expression><operator><numeric value> <numeric value> ::= <number>|<sign><number>|<numeric value><number> <operator> ::= <sign> | * | / <sign> ::= + | − <number> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Note: In this example, “+4−12*6” is interpreted as below. +4−12*6 → <code><number><sign><number><number><operator><number> → <numeric value><sign><numeric value><number><operator> <numeric value> → <numeric value><sign><numeric value><operator><numeric value> → <numeric value><operator><numeric value><operator><numeric value> → <expression><operator><numeric value><operator><numeric value> → <expression><operator><numeric value> → <expression> … interpreted as correct <expression> • Syntax diagram This is a diagram of a definition in BNF notation that is visually easy to understand. — p. 220 · Enlarge

Original BNF rules and derivation · 1 practice questions

p. 221

Original syntax diagrams for numeric value and expression. Below them, the syntax tree for +4-12*6 has subtraction at the root, left leaf +4 and right multiplication node with leaves 12 and 6. Source text: • Syntax tree This is a diagram of the results of syntactic analysis in a tree structure. An abstract tree structure especially refers to a tree structure that is composed of only the information that is required for semantic analysis. — p. 221 · Enlarge

(3) Semantic analysis This analyzes a tree structure generated in syntax analysis for meaning in terms of a programming language, and generates an intermediate code. Semantic analysis includes interpretation of sections that cannot be analyzed with the grammar of the programming language alone (e.g., validity of variable names, calling of external functions). In the intermediate code, the quadruple format or reverse Polish notation is sometimes used to represent formulas.

Original quadruple and Polish-notation worked examples. For s=4-12*6 the quadruples are (*,12,6,T1) and (-,4,T1,s). Reverse Polish notation is (s 4 12 6 * - =); prefix Polish notation continues on the next page. Source text: • Quadruple format (three-address statement) This is a method to represent an expression with four elements (i.e., operator, operand 1, operand 2, and result, including three variable addresses) in the form. For example, expression “s=4−12*6” is represented as below. (*, 12, 6, T1) (−, 4, T1, s) • Reverse Polish notation This is a notation method for formulas in which an operator is written after variables (or expressions) or numeric values as the subject of the operation. Since the order in which the operators appear is order of execution, it is used to represent formulas in a computer. (In some cases it is also used instead of a syntax tree.) There is also a notation method in which an operator is first written, which is called Polish notation. For example, an expression “s=4−12*6” is expressed as follows: Reverse Polish notation: (s 4 12 6 * − =) — p. 221 · Enlarge

p. 222

Original one-line continuation of the preceding source callout. Source text: Polish notation: (= s − 4 * 12 6) — p. 222 · Enlarge

(4) Optimization This analyzes intermediate code, modifies the program structure (e.g., expression simplification, composition modification), and optimizes the code so that it can be executed at a higher efficiency level. · 1 question

Original textbook callout or table. Source text: Optimization method Details This method expands the function to be called, at the Inline function expansion location where the function is called. This method calculates the value of an expression that Common subexpression exists in multiple locations as a variable for use in elimination operations, and replaces the expressions with this variable. This method replaces expressions consisting of Constant folding constants with the results of the expressions. Constant propagation This method replaces a variable with a constant. This method eliminates statements that have no effect Dead code elimination on the execution results. This method shifts an expression whose value does not Loop-invariant code motion change in a loop to outside of the loop. Loop unrolling This method expands the iteration process in a loop. — p. 222 · Enlarge

(5) Code generation This converts the optimized intermediate code into the target object code. Basically, the intermediate code is converted into machine language. However these days, it is temporarily converted to an intermediate code (e.g., byte code using Java byte code or CIL (Common Intermediate Language)), and then, upon execution, converted into an environment-dependent machine language.

Furthermore, depending on the intended use, the types of compilers below are available.

Original textbook callout or table. Source text: • Precompiler (preprocessor) This is a compiler that interprets additional (or supplemental) functions contained in a high-level language program, and then converts to a high-level language program before actual compilation. • Optimization compiler This is a compiler that focuses on the optimization of processing, and reduces the — p. 222 · Enlarge

p. 223

Original textbook callout or table. Source text: size and execution time of the object program after compiling as much as possible. • Cross compiler This is a compiler that generates an object program on one computer for another computer that has a different machine language. An assembler that is used for the same purpose is called a cross assembler. • Runtime compiler (JIT compiler (Just-In-Time compiler)) This is a compiler that translates a source program (i.e., source code) or intermediate code that is written in an intermediate language into a machine language just before its execution. It takes a somewhat long time at the start of execution, but it has the advantage of being able to execute a program without depending on the execution environment. — p. 223 · Enlarge

(3) Interpreter

An interpreter is a language processor that translates and executes a source program written in a high-level language one instruction on an instruction-by-instruction basis. The differences between a compiler and an interpreter are as below.

Original textbook callout or table. Source text: Compiler Interpreter Object program Generated Not generated One instruction at a time All statements at once (translation and execution Translation units (translation not possible if a possible even if the program is program is not completed) not completed) Execution speed Fast Slow Suitable application Batch processing Interactive processing — p. 223 · Enlarge

(4) Generator

A generator is a language processor that generates object programs by providing parameters, such as input data/output data specifications and process conditions. Since it can generate an object program without the need to be aware of the processing procedure, it is sometimes referred to as a non-procedural language.

(5) Translator

In the case of a language processor, a translator is software that converts a program into a

p. 224

different programming language. A compiler or an assembler can be called a translator that converts (i.e., translates) a source program into an object program. This does not apply to interpreters.

Section progress

Practice compiler optimization (1) Practice original bnf rules and derivation (1) Practice finite automata: input and internal state (1) Practice finite automaton transition diagram (1)

Original chapter exercises

Original chapter exercises →

New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015

ကိုယ်ပိုင်အကောင့်နဲ့
ဒေတာတွေကို Save ပါ

Video Lesson တွေက Haru အတန်းသားတွေအတွက်ပါ

FROM OUR STUDENTS

အတန်းမအပ်သေးပဲ Haru ဆီမှာ အစမ်းသင်ကြည့်ချင်ပါသလား?

သင်တန်းသားတွေရဲ့ စကားသံများ