AP Subject A 33 — Compilers and language processing: from lexical, syntax and semantic analysis to optimization

Based on the 2026 IPA Applied Information Technology Engineer Examination (AP), Subject A, Syllabus Ver.7.2; checked 2026-10-22. This is independent study material from Motitory: it is not affiliated with, reviewed or endorsed by IPA. It does not cover every item of Ver.7.2 and does not guarantee a pass. All examples and questions here are Motitory originals, not IPA past questions.

Study index

1. Role of the compiler and the processing flow
2. Lexical analysis
3. Syntax analysis and grammars
4. Semantic analysis
5. Intermediate representation and optimization
6. Code generation and the object program
7. Terminology table
8. Quick sheet and traps
9. Five original diagnostic questions
10. Self-check and review schedule
11. Official sources

This is AP33 (a supplement) of the fixed AP33–38 completion plan, not the last article of the series; every installment is listed in the series hub. Data structures such as trees and stacks were covered in AP5, tracing state-transition tables in AP6, and development methods and testing in AP23. They are not retaught here; this article covers only what is specific to compilers.

1. Role of the compiler and the processing flow

A compiler (コンパイラ) translates a source program (ソースプログラム) written in a high-level language into an object program (目的プログラム) for the target machine, without changing its meaning. Linking commonly turns object programs into an executable. The standard exam model is this sequence:

Source program (characters)
 → ① Lexical analysis : characters → token stream
 → ② Syntax analysis  : tokens → syntax tree (parse tree / AST)
 → ③ Semantic analysis: declaration, type and context checks; symbol table
 → ④ Intermediate code: AST → intermediate representation (e.g. three-address code)
 → ⑤ Optimization     : improve the IR while keeping observable behaviour
 → ⑥ Code generation  : object code for the target machine
Object program

Real compilers may merge phases or run optimization several times, so treat this order as a study model for “what each phase takes in and what it produces”.

2. Lexical analysis

Lexical analysis (字句解析) cuts the character sequence into tokens (トークン); whitespace and comments are discarded here. Token kinds (identifiers, numbers, operators, delimiters) are usually defined by regular expressions and recognized by a finite automaton (有限オートマトン), e.g. identifier = letter (letter | digit)*. Tracing a finite automaton’s transition table by hand was covered in AP6.

• Longest match: <= is read as one token, not as < followed by =.
• A lexical error example: a character that fits no token pattern (such as # where the language does not allow it).

Worked example 1 — tokens and a syntax tree

Source: total = price * 3 + tax;

#	Token kind	Text
1	identifier	total
2	assignment operator	=
3	identifier	price
4	multiplication operator	*
5	number	3
6	addition operator	+
7	identifier	tax
8	delimiter	;

The six spaces do not become tokens, so the result is 8 tokens. The tree is built in the next section.

3. Syntax analysis and grammars

Syntax analysis (構文解析), or parsing, checks that the token stream follows the grammar and builds its structure as a tree. Programming-language syntax is usually written as a context-free grammar (文脈自由文法) in BNF.

stmt   → id = expr ;
expr   → expr + term   | term
term   → term * factor | factor
factor → id | num | ( expr )

• Because * sits on a lower level (term), it binds before + (precedence).
• Because the rule is left-recursive (expr → expr + term), operators on the same level group from the left (left associativity). If - were added on the level of +, a - b - c would mean (a - b) - c.
• A grammar without levels, such as E → E + E | E * E | id, is ambiguous: a + b * c gets two different trees.

The abstract syntax tree (AST) for example 1:

        =
       / \
   total   +
          / \
         *   tax
        / \
    price   3

A parse tree keeps every nonterminal such as expr and term as a node; an AST keeps only operations and operands. Parentheses and ; disappear from the AST because the tree shape already records the structure.

Formal languages and automata (a frequent exam pairing):

Language class	Defined by	Recognized by	Used in the compiler for
Regular	regular expressions / regular grammar	finite automaton	lexical analysis (tokens)
Context-free	context-free grammar (BNF)	pushdown automaton (stack)	syntax analysis

A finite automaton has finitely many states, so it cannot match arbitrarily deep nested parentheses. Nesting needs a stack, which is why parsing uses context-free grammars.

4. Semantic analysis

Semantic analysis (意味解析) checks whether a grammatically correct tree obeys the language’s meaning rules. Declarations are recorded in a symbol table (記号表).

• Use of an undeclared name; a duplicate declaration in the same scope
• Type checks: assigning a string to an integer variable; wrong number or type of arguments
• Inserting an implicit conversion (e.g. integer → real) into the tree where the language requires it

“A name must be declared before use” depends on surrounding context and is hard to express with a context-free grammar alone, so it is checked in semantic analysis rather than parsing. Conversely, a logic error — correct syntax and types, wrong algorithm — is normally not found by the compiler; it belongs to testing (AP23).

5. Intermediate representation and optimization

An intermediate language (中間言語) or intermediate representation sits between the source language and the target machine and is usually not tied to a specific CPU. The same IR can therefore feed code generators for several machines, and machine-independent optimizations are written once. A typical form is three-address code (3番地コード): one operator and at most three addresses per instruction—one result and up to two input operands.

Worked example 2 — three-address code and safe optimization

Assume b and c are integer inputs and x, y and z are integer locals. None of the shown calculations overflows, and there are no calls, I/O or volatile accesses.

x = 4 * 2;
y = (b + c) * (b + c) - x;
z = y + 1;      // z is never read afterwards
return y;

① Three-address code (10 lines)

t1 = 4 * 2
x  = t1
t2 = b + c
t3 = b + c
t4 = t2 * t3
t5 = t4 - x
y  = t5
t6 = y + 1
z  = t6
return y

② Constant folding (定数畳み込み) and constant propagation: 4 * 2 can be computed as 8 at compile time. Since x never changes, t5 = t4 - x becomes t5 = t4 - 8.

③ Common-subexpression elimination (共通部分式の除去): b and c do not change between t2 and t3, and integer + has no side effects, so t3 = b + c is removed and t2 reused. If the expression were a call like f() that prints or changes state, merging would change how many times it runs, so it is not allowed.

④ Dead-code elimination (デッドコード除去): z and t6 are never read and computing them has no side effects, so they go. After ②, x and t1 are no longer read either, so they go too. Code that produces behaviour the language defines — output, an exception — cannot be removed just because its result is unused.

⑤ Result (4 lines)

t2 = b + c
t4 = t2 * t2
y  = t4 - 8
return y

Check: with b = 1, c = 2, the original gives (3) * (3) - 8 = 1 and the optimized code 9 - 8 = 1.

The rule of optimization: it must preserve the language-defined observable behaviour (output, return values, order of I/O and so on). It is also not guaranteed to make every program faster: transformations that grow code, like inlining or loop unrolling, can hurt cache behaviour, and compile time rises. Confirm the effect by measuring. Other names to recognize: loop-invariant code motion (ループ内不変式の移動) and strength reduction (e.g. x * 2 → x + x).

6. Code generation and the object program

Code generation (コード生成) turns the IR into target-machine instructions; instruction selection and register allocation are the core tasks. The resulting object program is normally not run as is: a linker (リンカ) combines it with other object modules and libraries into an executable load module.

• Interpreter (インタプリタ): runs the source program (or intermediate code) by interpreting it, without producing an object program.
• Cross compiler: produces object code for a machine other than the one the compiler runs on.

7. Terminology table

English	日本語	한국어	One-line definition
compiler	コンパイラ	컴파일러	translates a source program into an object program
lexical analysis	字句解析	어휘 분석	characters → tokens
token	トークン	토큰	smallest meaningful unit: identifier, number, operator
syntax analysis (parsing)	構文解析	구문 분석	tokens → tree under the grammar
abstract syntax tree	抽象構文木	추상 구문 트리	tree keeping only operations and operands
context-free grammar	文脈自由文法	문맥 자유 문법	grammar for syntax, written in BNF
formal language	形式言語	형식 언어	set of symbol strings defined by a grammar or machine
automaton	オートマトン	오토마톤	abstract machine that reads input and changes state
semantic analysis	意味解析	의미 분석	checks declarations, types and context rules
symbol table	記号表	기호표	stores names with type and scope information
intermediate language	中間言語	중간 언어	representation between source and machine code
three-address code	3番地コード	3번지 코드	one operation, one result address and up to two input addresses
optimization	最適化	최적화	improves code while keeping behaviour
code generation	コード生成	코드 생성	IR → target-machine instructions
object program	目的プログラム	목적 프로그램	the compiler’s output

8. Quick sheet and traps

• Lexical = characters→tokens (regular, finite automaton) / syntax = tokens→tree (context-free, stack) / semantic = declarations and types / code generation = target instructions.
• Classifying errors: disallowed character → lexical; missing parenthesis → syntax; undeclared name or type mismatch → semantic; wrong result → logic error (testing).
• Precedence comes from grammar levels; associativity from the direction of recursion.
• Three-address code = one operator per instruction, with temporaries t1, t2, ….
• Constant folding = compute at compile time; CSE only with no side effects or intervening updates; dead-code elimination only when there is no observable effect.
• Traps: “optimization always speeds things up”, “an intermediate language is a specific CPU’s machine code”, “object program = source program”, “a finite automaton can check nested parentheses”.

9. Five original diagnostic questions

These questions were written by Motitory; no IPA past question is used or adapted.

Q1 — Phases

Which phase skips whitespace and comments in the source text and splits it into units such as count, <= and 10?

A. Syntax analysis

B. Semantic analysis

C. Lexical analysis

D. Code generation

• A: Wrong. Parsing groups an already split token stream into a tree under the grammar.
• B: Wrong. Semantic analysis checks declarations and types after tokenizing and parsing.
• C: Correct. Characters → tokens; by longest match <= is a single token.
• D: Wrong. Code generation is a late phase that produces target instructions from the IR.

Q2 — Grammar and precedence

Using the grammar of section 3, which is the correct AST for a + b * c?

A. Root *, left child a + b, right child c

B. Root + with a, b and c all as its children

C. The grammar is ambiguous, so both trees are valid results

D. Root +, left child a, right child b * c

• A: Wrong. That is the tree for (a + b) * c; without parentheses this grammar cannot produce it.
• B: Wrong. A binary operator node has two children; putting three under one node loses the order of operations.
• C: Wrong. The expr/term/factor levels remove the ambiguity. The level-free E → E + E | E * E | id would have been ambiguous.
• D: Correct. * is grouped first on the lower term level.

Q3 — Where the error is detected

Which of the following is typically detected in semantic analysis?

A. A closing parenthesis is missing, as in if (x > 0 {.

B. An undeclared variable totl is used because of a typo.

C. An identifier contains #, a character the language does not allow.

D. A loop condition is off by one, so the total comes out 1 too small.

• A: Wrong. It breaks the grammar, so parsing detects it.
• B: Correct. totl is a valid identifier token and fits the grammar, but the symbol table has no declaration for it.
• C: Wrong. The character fits no token pattern, so lexical analysis detects it.
• D: Wrong. It breaks no language rule; it is a logic error found by testing, not by the compiler. Review testing in AP23

Q4 — Safe optimization

A function uses only integer local variables, and log() prints to the screen. Which transformation does not change behaviour?

A. Replace t = 6 * 7 with t = 42.

B. Replace log(x) + log(x) with 2 * log(x).

C. Delete the statement log(x); because its return value is unused.

D. Make maximum optimization the default without measuring, because optimization makes every program faster.

• A: Correct. Constant folding computes the same value at compile time; observable behaviour is unchanged.
• B: Wrong. Output drops from two calls to one. An expression with side effects cannot be merged as a common subexpression.
• C: Wrong. Output is observable behaviour, so the call is not dead code even though its result is unused.
• D: Wrong. Larger code and longer compile time are real costs, and no program is guaranteed to get faster; measure.

Q5 — Formal languages and automata

Which statement is correct?

A. A finite automaton alone is enough to check arbitrarily deep nested parentheses such as ((())).

B. An intermediate language is always a specific CPU’s machine code, so it cannot be retargeted.

C. Regular languages are recognized by finite automata and used in lexical analysis; context-free grammars correspond to pushdown automata with a stack and are used in syntax analysis.

D. The object program is the source program before lexical analysis.

• A: Wrong. With finitely many states it cannot count unbounded nesting; a stack is needed. Review the stack as a data structure in AP5.
• B: Wrong. An intermediate language is usually machine-independent, which is why it serves several targets and shared optimizations.
• C: Correct. This is the pairing of language class, recognizer and compiler phase. Review state-transition tracing in AP6.
• D: Wrong. The object program is the compiler’s output; the source program is its input.

Answers: C, D, B, A, C

10. Self-check and review schedule

• I can state the input and output of each of the six phases in order.
• I can redraw the 8 tokens and the AST of total = price * 3 + tax;.
• I can explain precedence and associativity from grammar levels and recursion direction.
• I can classify example errors as lexical, syntax, semantic or logic.
• I can reduce example 2 from 10 lines to 4 and say why each step is safe.
• I can pair regular languages with finite automata and context-free grammars with pushdown automata.

Recommended review cycle (separate from the publication schedule): same day, redo examples 1 and 2 without looking → day 1, Q1–Q5 → day 3, fill in the terminology table from the quick sheet alone → day 7, write three-address code for a new expression and optimize it → day 14, revisit only the questions you missed.

11. Official sources

• IPA Applied Information Technology Engineer Examination Syllabus Ver.7.2 — 大分類1 / 中分類1 / 3. 情報に関する理論 / (10) コンパイラ理論, PDF p.10 (printed page -6-). Checked for the role and process of a compiler, lexical, syntax and semantic analysis, code generation and optimization, and the terms context-free grammar, intermediate language, object program, formal language and automaton. Checked 2026-10-22.
• IPA syllabus hub — checked 2026-10-22.

This is the first installment of the AP33–38 completion plan. The next planned topic is AP34 wireless LAN, and the series ends with AP38.