Shulou(Shulou.com)06/03 Report--

This article mainly introduces "how to solve the First set of C++ compilation principles". In daily operation, I believe many people have doubts about how to solve the First collection of C++ compilation principles. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts of "how to solve the First collection of C++ compilation principles". Next, please follow the editor to study!

Catalogue

1. Boarding requirements

2. Principle

3. Some ideas and optimization.

4. Code

4.1 lan.txt file content

4.2 lan.txt file content

1. Boarding requirements

Objective: to master the top-down syntax analysis method, and can be realized by program.

Request:

For example, the grammar used is as follows:

Write First function to realize its solving process.

E-> TE'

E'- > + TE' | #

T-> FT'

T'- > * FT' | #

F-> (E) | id

End

Tip:

The non-Terminator is an uppercase letter; or an uppercase letter followed by'

Terminators are lowercase letters and symbols (+, *)

Deduces that the symbol → is or->

End the grammar with end.

Do not write first functions for specific grammars.

2. Principle

A-> a, add a to First (A)

A-> Y1Y2 ·Yn

Add the characters of First (Y1) except the empty string to First (A), if 1 =

< i < n - 1，Y1，Y2， Yi中均含有空串，则将First(Yi + 1)加入到First(A)中，若Y1，Y2，···，Yn都有空串，则将空串加入到First(A)中 First(a) = {a} 3、一点思路及优化 将输入格式化（扫描输入） 将产生式转换为哈希map： 对任一产生式： A ->

Body_1 | body_2 | | body_n

Use An as the key of map

The value of map is a vector of a string class (vector)

Add body_1,body_2, body_n, and body_n to value.

Solving First (str)

Special case handling, str is empty or str is not in the production key, return null; the first character of str is the Terminator, returns the collection of the first character.

In general, get the generator set bodys derived by str (each generator is body), and traverse the generator set to solve the First set

For the empty string, we add the tag hasBlank = true and iterate through the characters of body

The first character of body is the Terminator, which is added directly to the first set, marking hasBlank = false to traverse the next body, if any.

The first character of body is a non-Terminator. Recursively solve the non-Terminator first set and mark it as temp. At the same time, mark the empty string as false, add the characters except the empty string in temp to the first set; if there is an empty string in temp, mark the empty string as true, and continue to traverse the characters of the current body. In terms of understanding, the string after body can be regarded as a new body to proceed with the solving step.

After traversing the characters of body, if the empty string tag hasBlank is still true, the empty string will be added to the first set.

Optimization: the intermediate result of the recursive solution can be placed in the global hash first (or change the name to avoid conflicts) to avoid repeated iterations (this code is not implemented, it will be next time).

4. Code / * * @ brief Function for generating set of First (a) @ author the Beginning of Autumn piggy * @ time: 2021-10-13 * @ notice: it is required that there must be no space in the generating body sentence pattern * there must be an empty string in the production body of left recursion (it must be able to terminate) * char'# 'act as varepsilon * * / # include # include using namespace std;unordered_map P / / the set of production P void scan () {/ / scan function implements the scan grammar from the file, adding the corresponding production to the mapping P fstream fs; string input; fs.open ("lan.txt"); if (! fs.is_open ()) {/ / file opening failed cout input; while (input! = "end") {string VN = input / / non-Terminator fs > > input; / / Skip derivation symbol if (input! = "- >" & & input! = "→") {cout input & & input = = "|") {fs > > input; P [VN] .emplace _ back (input) } / / void generate () {/ /} unordered_set First (const string& str) {/ / Terminator and empty string, whether has the VN or not if (str = "" | str = = "#" | | P.find (str) = = P.end ()) return {}; if (! (str [0] > ='A'& str [0] bodys unordered_set res = {}) For (auto & s: bodys) {bool hasBlank = whether the true;// contains an empty string, and whether to continue reading the producer for (int I = 0; I)

< s.size() && hasBlank; ++i){ if(s[i] >

='A'& & s [I]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.