JPH0455944A - Production of syntactic analysis part of compiler - Google Patents

Abstract

PURPOSE:To attain the syntactic analysis with use of a single LR(1) syntactic analysis table by putting a dummy token into the grammar used for production of an LR(1) syntactic analysis subroutine in order to show the type of the grammar to be analyzed and then treating plural grammars in common with each other. CONSTITUTION:A dummy token is put into the grammar used for production of an LR(1) syntactic analysis subroutine in order to show the type of the grammar to be analyzed. So that plural grammars can be treated in common with each other. For instance, a grammar 'S E¦bC¦cI' is added. In this case, (a - c) show the dummy tokens. Thus E showing an arithmetical formula C showing a conditional formula, and I showing a unique name are all reduced to a start symbol S. Then the syntactic analysis can be attained with use of a single LR(1) syntactic analysis table.

Description

[Detailed Description of the Invention] [Summary] Regarding a method for creating a part of the parsing section of a compiler using the LR(1) parsing method, multiple grammars are combined into a single LR(1) parsing table. For the purpose of making it possible to analyze using the LR (
1) When creating using the syntax analysis method, if there are multiple grammars to be analyzed in the part that uses the LR(1) syntax analysis subroutine, analyze the grammar to create the LR(1) syntax analysis subroutine. L that parses multiple grammars by inserting tokens that indicate the type of grammar.
An R(1) parsing table is generated (step 1), and when calling the LR(1) parsing subroutine that includes this LR(1) parsing table, the purpose is determined by inserting the type of grammar to be analyzed. (step 2).

[Industrial Application Field] The present invention relates to a method for creating a part of a parsing section of a compiler using the LR(1) parsing method.

[Prior Art] The LR(1) parsing method is the most powerful and practical method for automatically generating the parsing section of a compiler using a computer or the like. The LR(1) parsing method is a method in which a character string is read from the left, interpretation is performed from the right, and when determining the next action, the next word is read. However, in the absence of a powerful optimizer (optimization tool), if the entire syntax analysis section is created using the LR(1) syntax analysis method, the LR(1) syntax analysis table used as an automatic syntax generation tool will become enormous. or the analysis speed may slow down.

FIG. 5 is a conceptual diagram of the LR(1) syntax analysis table.

As shown in the figure, it is composed of "state" and "word".
It describes what to do when a certain word comes under certain conditions. For example, in the shaded part of the diagram determined by a certain word in a certain state, the following transition is performed.

■Read one word and proceed to state n.

■Read one word, put it on the stack and proceed to state n.

■Reduction processing: For example, in the syntax rule A-A+C, A
Analyze +C, reduce the result to A, and at the same time +a,
Generates a code called c.

By the way, part of a language does not necessarily have to be an LR(1) grammar; depending on the grammar, the operator rank method, which has many restrictions but is simple, or the LL(1) parsing method may be sufficient. There is also. The operator ranking method is +, -, x
This allows operators such as , ÷ to be prioritized and parsed.

The LL (1) parsing method is a method in which a certain character string is read from the left, interpretation is also performed from the left, and when determining the next action, the next word is read.

Therefore, when creating a compiler, multiple parsing methods may be mixed. LR (
1) When creating using the syntactic analysis method, although they are different grammatical elements, they are related to each other, so they can be combined into one
It may be more convenient to parse with one parsing routine. For example, suppose there are three grammars shown below.

■ Grammar 1 (arithmetic expression E → E + 111 (1) ■ Grammar 2 (conditional expression) % expression % (2) Here, 1 means "or". - Significant name refers to a fixed value such as data. When performing syntax analysis using these grammars, an LR(1) syntax analysis table is required for each grammar.However, as is clear from the above formula, unique names are used for arithmetic expressions, and conditional expressions are Also, an arithmetic expression is used for -signature.In this way, grammars are often related to each other.In such cases, the three grammars also use the same LR (1) It is clear that it is more convenient to analyze with a syntax analysis routine using a syntax analysis table.

[Problem to be solved by the invention] However, when creating a part of the parsing section of a compiler as a subroutine using the LR(1) parsing method, there is a problem that multiple grammars cannot be analyzed. . This will be explained in detail. For example, to check whether the character string i-i+i satisfies the above grammar, a tree as shown in FIG. 6 is created. If the string finally ends with E, the character string can be parsed using LR(1).

When performing such syntax analysis, the grammar G is fvN.

It consists of four elements: V, , P, and S+.

VN; Character string VT that appears in the middle of E, T, F, etc.
: l + -+ character string P that finally appears in tens etc.; start symbols of rules S, E, etc. If you create a subroutine that parses a certain grammar, it will eventually return to the first symbol (.However, The start symbol differs depending on the type of grammar (arithmetic expression 9 conditional expression, etc.).The compiler process returns to the start symbol, so if the start symbol is different, a single LR(1) parsing table can contain multiple start symbols. could not parse the grammar.

The present invention has been made in view of these problems, and provides a method for creating a syntax analysis section of a compiler that can analyze multiple grammars using a single LR(1) syntax analysis table. is intended to provide.

[Means for Solving the Problems] FIG. 1 is a flowchart showing the principle of the method of the present invention. In the case where a part of the syntax analysis section of a compiler is created using the LR(1) syntax analysis method, and there are multiple grammars to be analyzed in the part that uses the LR(1) syntax analysis subroutine, the LR(1) syntax analysis subroutine is 1) Generate an LR(1) parsing table for parsing multiple grammars by inserting a token indicating the type of grammar to be analyzed into the grammar for creating the parsing subroutine (step 1); LR(1) containing this LR(1) parsing table
The present invention is characterized in that when calling the parsing subroutine, the type of grammar to be analyzed is inserted to parse the target grammar (step 2).

[Operation LR (1) A dummy token indicating the type of grammar to be analyzed is inserted into the grammar used to create the parsing subroutine so that multiple grammars can be handled in common. For example, in addition to the above-mentioned expressions (1) to (3), the following grammar is added: 5-aE I bCl c I (4). Here, a, b.

C is a dummy token. As a result, E denoting an arithmetic expression, C denoting a conditional expression, and ■ denoting a unique name are all reduced to the start symbol S, making it possible to perform syntax analysis using a single LR(1) syntax analysis table. .

[Example] Hereinafter, an example of the present invention will be described in detail with reference to the drawings.

Arithmetic expression 1 In the case of a subroutine that analyzes a conditional expression and a data name (-signature), the arithmetic operator includes the data name as a component, the conditional expression includes the arithmetic expression and the data name as a component, and the data name is a subscript. They are related to each other, such that they include arithmetic expressions. If G is a grammar for analyzing such a subroutine, the definition of grammar G is as follows.

P is G-(VN, VT, P, 5) VN = (S, E, C, 11 V↑-((1+ 1.-1 C+)+ a+ b+ 01C is a dummy token S-→aElbclcl E4E+II C →E−E ■→i (E) Here, a and b in the above equation.

These are terminal symbols that indicate the analysis of each arithmetic expression, nine conditional expressions, and data name. Based on the grammar shown in (5) to (11), L
By creating the R(1) syntax analysis table, it is possible to create a subroutine that analyzes the arithmetic expression 1 conditional expression and data name. Now let's create a subroutine.

The arithmetic expression E shall be represented by the symbol E, the symbol 10, the symbol I, or the symbol ■, and shall be expressed as E-E+I I I (12). Below, conditional expression 〇 and data name I will be considered in the same way and expressed as C4E-E(13) I-i (E) (14). Also, considering that S is generated from S', we add the generation rule S'→S (15). In these grammars, things generated from E include, for example, i+i+i, i, and things generated from C include, for example, i-i, i+
There is i-i, and what is generated from ■, for example, ii (
There is i).

■ A state where you are not reading anything. , the state where a is read from Io is I, the state where b is read from Io is I2■ the state where i is read from 1 is 13, then the GOTO statement (transition) that determines the state and destination as shown in Figure 2 destination) is created. - indicates how far the token has been read. This is LR
(1) It becomes a syntax analysis table. If the next token is not C in state I3, an object code of i is generated.

Note that when calling this subroutine, arithmetic expression 2 conditional expression, arithmetic expression 1 conditional expression, and arithmetic expression 1 conditional expression, by passing tokens indicating a, b, c to the subroutine instead of the first token of data name, as the first token. Data names can be parsed.

For example, if you pass the token a to a subroutine, it will start analyzing it, thinking it is an arithmetic expression. Also, if you pass the token b to the subroutine, it will think it is a conditional expression and start analyzing it.

FIG. 3 is a flowchart showing the token reading process in the subroutine. First, it is checked whether the character string is being read for the first time (Sl). If it is the first time, dummy token addition processing according to the present invention begins. That is, it checks whether the character string is a conditional expression (S2), and if so, returns cnd of the token indicating the conditional expression (S3).

Next, if it is not a conditional expression, it is checked whether it is an arithmetic expression (S4), and if so, the art of the token indicating the arithmetic expression is returned (S5). Next, if it is not an arithmetic expression, only the data name remains, so
The data of the token indicating the data is returned (S6). If this is not the first time the character string has been read, there is no need to return a dummy token, and the read token may be returned as is (S7).

FIG. 4 is a diagram showing an example of the configuration of a compiler used in the present invention. In the figure, 1 is a lexical analysis unit that analyzes a read character string, 2 is a syntax analysis unit that characterizes the present invention, 3 is a semantic analysis unit, 4 is an optimization unit, and 5 is a target code generation unit. The syntax analysis section 2 is composed of a syntax analysis main body 2a, a syntax analysis subroutine 2b, and a dummy token addition section 2c.

The parsing body 2a does not include the LR(1) parsing section. LR(1,) syntax analysis is performed in the syntax analysis subroutine 2b. In addition, the parsing subroutine 2b includes:
The above-mentioned LR(1) parsing table is included.

In the system configured as described above, a character string is first read into the lexical analysis section 1. The read character string is lexically interpreted and then input to the syntactic analysis unit 2. Syntax analysis section 2
Then, add an arithmetic expression 1 to the beginning of the input character string according to the type of conditional expression and data name, and add a dummy code part 2c to the beginning.
A dummy Kun is added. Then, the character string to which the dummy token has been added is analyzed by the syntax analysis subroutine 2b, and then passed to the syntax analysis main body 2a.

In this case, since all grammars are reduced to the same starting symbol, they can be analyzed using a common LR(1) analysis table.

The results analyzed by the syntactic analysis unit 2 are then passed to the semantic analysis unit 3, where the meaning is analyzed. Thereafter, the optimization section 4 performs optimization processing, and then the object code generation section 5 generates an object code.

[Effects of the Invention] As described above in detail, according to the present invention, LR (
1) By inserting a dummy token indicating the type of grammar to be analyzed into the grammar used to create the parsing subroutine so that multiple grammars can be handled in common, E, which indicates an arithmetic expression, also indicates a conditional expression. Since both C and I indicating a unique name return to the start symbol S, syntax analysis can be performed using a single LR(1) parsing table.

[Brief explanation of the drawing]

Fig. 1 is a flowchart showing the principle of the method of the present invention, Fig. 2 is a diagram showing a state diagram and call statement, Fig. 3 is a flowchart showing token reading processing in a subroutine, and Fig. 4 is a compiler used in the present invention. FIG. 5 is a conceptual diagram of an LR(1) syntax analysis table, and FIG. 6 is an explanatory diagram of a character string analysis method. In Figure 4, 1 is a lexical analysis section, 2 is a syntax analysis section, 2a is a syntactic analysis body, 2b is a syntactic analysis subroutine, 2c is a dummy token addition section, 3 is a semantic analysis section, 4 is an optimization section, 5 is a syntax analysis section This is the target code generator.

Claims (1)

[Claims] When a part of the parsing section of a compiler is created using the LR(1) parsing method, and there are multiple grammars to be analyzed in the part that uses the LR(1) parsing subroutine, An LR(1) parsing table for parsing multiple grammars is generated by inserting a token indicating the type of grammar to be analyzed into the grammar for creating the LR(1) parsing subroutine (step 1). ), LR(1) containing this LR(1) parsing table
A method for creating a syntax analysis section of a compiler, characterized in that when calling a syntax analysis subroutine, a target grammar is analyzed by inserting the type of grammar to be analyzed (step 2).