1024programmer Asp.Net [Algorithm] Letters from afar, from mathematical expression algorithms to assembly syntax interpreters

[Algorithm] Letters from afar, from mathematical expression algorithms to assembly syntax interpreters

[Algorithm] Letters from afar, from mathematical expression algorithms to assembly syntax interpreters

In the bustling city, Xiaoyue, as a software engineer, is busy every day in this reinforced concrete forest. Her life seems to be filled with work and all kinds of trivial things, but in this busy life, she can always find some small fun outside of work.

After work that day, Xiaoyue received an email from her foreign classmate Sophie. The content of the email took her mind back to her college days when she was learning assembly language.

Sophie is a very smart girl, and the two of them became good friends in college. Sophie has a strong interest in programming, while Xiaoyue has a special liking for theoretical knowledge. In the computer-based exam in the final year of college, the two of them collaborated to complete an algorithm for a mathematical expression through the reverse Polish expression algorithm.

This expression algorithm was implemented by Xiaoyue in the computer-based exam. It is mainly used to solve mathematical calculation problems. But looking back now, she feels that there is still much room for improvement in this algorithm, and she can even develop her own scripting language interpreter based on it. So she decided to use her spare time to improve the algorithm.

Among many practical programming projects, page script interpreters and SQL language interpreters are two popular choices. However, the syntax of these two projects is relatively complex, so Xiaoyue decided to start researching from a simpler assembly language interpreter.

Xiaoyue began to study the grammar and instruction set of assembly language carefully. She wanted to use cSharp to write her own assembly grammar interpreter. She knew that implementing an assembly syntax interpreter was not an easy task, but she also firmly believed that as long as she continued to work hard and explore, she would be able to succeed.

In the process of implementing the assembly syntax interpreter, Xiaoyue referred to a large number of materials and documents and constantly adjusted and improved her code. She encountered many difficulties and setbacks, but she never gave up. Whenever she encounters a problem, she will think of Sophie and the arithmetic expression algorithm, which gives her the motivation to keep moving forward.

After a period of hard work, Xiaoyue finally succeeded in writing his own assembly syntax interpreter. This interpreter can parse assembly language syntax and perform corresponding operations based on the syntax entered by the programmer.

After Xiaoyue’s best friend Xiaoxin saw her results, she joked: “You are really a heroine in the programming world!” Xiaoyue smiled after hearing this, and couldn’t help but think of Sophie. She thought: “If Sophie was still in China, we would definitely have more opportunities for cooperation.”

However, life is always full of unknowns and variables. After graduation, Sophie chose to work and live abroad, while Xiaoyue continued her career as a software engineer in China. Although the two have rarely contacted each other, Xiaoyue has always treasured their friendship and the mathematical expression algorithm in the computer exam.

In the process of Xiaoyue implementing the assembly syntax interpreter, she not only improved her programming skills, but also further understood the principles and implementation methods of arithmetic expression algorithms. She believes that this experience will be a valuable asset in her future career.

Today, Xiaoyue is no longer the girl who programmed simply to cope with exams. She has her own pursuits and dreams in the field of programming. She hopes to become a better software engineer through her own efforts and continuous learning, and contribute to this digital era.


The assembly interpreter syntax that Xiaoyue needs to implement is as follows:

mov x, y – Copies y (whether an integer or a register value) into the register (variable) x.
inc x – increments the contents of register x by 1.
dec x – Decrement the contents of register x by 1.
add x, y – Add the contents of register x to y (whether an integer or the value of a register) and store the result in x (i.e. register[x] += y).
sub x, y – subtracts y from register x (either an integer or the value of the register) and stores the result in x (i.e. register[x] -= y).
mul x, y – same as multiplication (i.e. register[x] *= y).
div x, y – same as integer division (i.e. register[x] /= y).
label: – Defines the function label position, generally used for function positioning (label = identifier + colon, the identifier is a string that does not match any other command). Jump commands and calls target these label locations in the program.
jmp lbl – jump to custom function label lbl.
cmp x, y – Compares x (whether an integer or a register value) with y (whether an integer or a register value). The results are used for conditional jumps (jne, je, jge, jg, jle and jl).
jne lbl – Jump to label lbl if the values ​​of the previous cmp command are not equal.
je lbl – Jump to label lbl if the values ​​of the previous cmp command are equal.
jge lbl – jump to label lbl if x is greater than or equal to y in previous cmp command.
jg lbl – jump to label lbl if x is greater than y in previous cmp command.
jle lbl – jump to label lbl if x is less than or equal to y in previous cmp command.
jl lbl – jump to label lbl if x is less than y in previous cmp command.
call lbl – Calls the subroutine identified by lbl. when.TryGetValue(y, out yop) )
220 yop = 0 ;
221
222 registers[x] = op(registers[x], IsNum(y) ? int.Parse(y) : yop);
223 }
224
225 private static string FormatMessage(List< string> lst)
226 {
227 return span> string.Join(“” , lst.Select(s => registers.ContainsKey(s) ? registers[s].ToString() : (IsNum(s) ? s : s.Substring(1, s.Length – 2))));
228 }
229 }
230
231
232 #endregion
233
234 private string displayProg(string p)
235 {
236 Console.WriteLine(\n———————\ n);
237 Console.WriteLine (p);
238 return span> p;
239 }
240 }

The random test algorithm RandomTests() in the test case tests the correctness of the interpreter by generating random program codes. Specifically, it generates a basic program code template `BASE_PROG`, in which three register variables, an operator and a jump condition are randomly selected to randomly generate a new program code. The generated program code contains some basic instructions, such as mov, call, msg, cmp, ret, etc., as well as randomly selected operators and jump conditions. The generated program code will be passed to two interpreters (InternalAssembler and AssemblerInterpreter) for interpretation and execution, and then their output results will be compared to see if they are consistent.

Specifically, the process of generating program code is as follows:
1. Randomly select three different register variables from the predefined variable array `VARS`.
2. Randomly select an operator from the predefined operator array `OPERATIONS`.
3. Randomly select a jump condition from the predefined jump condition array `JUMPS`.
4. Fill in the basic program code template `BASE_PROG` with randomly selected register variables, operators and jump conditions to generate a new program code.

The generated program code will contain randomly selected register variables, operators and jump conditions, as well as some fixed instructions, such as mov, call, msg, cmp, ret, etc. The generated program code will be passed to two interpreters for interpretation and execution, and their output results will be compared to see if they are consistent. If the output results of the two interpreters are inconsistent, the generated program code will be output for debugging and analysis.


RamdomTests() tests randomly to ensure that two different interpreters (InternalAssembler and AssemblerInterpreter) expect the same An assembly language program can produce the same result.

  1. Test case: In this code, 1024 random assemblies are generated through a loop (for (int i = 0; i < 1024; i++)) Program (randProg). Each such program is used to test two interpreters simultaneously: InternalAssembler and AssemblerInterpreter.
  2. Comparison of expected value and actual value: For each randomly generated program, two results were obtained at the same time: one is the interpretation of the interpreter InternalAssembler defined in the test class result (expected), and the other is the interpretation result of AssemblerInterpreter (actual ). The two results were then compared.
  3. Check the results: If the results of the two interpreters are different (expected != actual), then the problematic program will be printed (displayProg(randProg)). An assertion (Assert.AreEqual(expected, actual)) is then used to confirm whether the two results are consistent. If the two results match, the test passes; otherwise, the test fails.

The necessity of testing methods to compare the results of two interpreters is:

  • Ensure correctness: By comparing the results of the two interpreters, you can confirm whether they can both interpret the assembler correctly. If there are any inconsistencies, the reasons can be immediately discovered and investigated, thus improving the accuracy of the interpreter.
  • Performance comparison: Although this code does not explicitly compare execution times, you can compare their performance somewhat indirectly by running both interpreters simultaneously and comparing the results. If one interpreter is always faster than the other, consider optimizing it.
  • Consistency: Even if the results of two interpreters are correct, there may be slight differences due to different implementations. By comparing these differences, you can ensure consistency in their implementation and avoid potential confusion and errors.

Overall, this comparison is an effective testing strategy to ensure the correctness and consistency of interpreters, while also allowing some degree of evaluation of their performance.

The same assembly language program can produce the same results.

  1. Test case: In this code, 1024 random assemblies are generated through a loop (for (int i = 0; i < 1024; i++)) Program (randProg). Each such program is used to test two interpreters simultaneously: InternalAssembler and AssemblerInterpreter.
  2. Comparison of expected value and actual value: For each randomly generated program, two results were obtained at the same time: one is the interpretation of the interpreter InternalAssembler defined in the test class result (expected), and the other is the interpretation result of AssemblerInterpreter (actual ). The two results were then compared.
  3. Check the results: If the results of the two interpreters are different (expected != actual), then the problematic program will be printed (displayProg(randProg)). An assertion (Assert.AreEqual(expected, actual)) is then used to confirm whether the two results are consistent. If the two results match, the test passes; otherwise, the test fails.

The necessity of testing methods to compare the results of two interpreters is:

  • Ensure correctness: By comparing the results of the two interpreters, you can confirm whether they can both interpret the assembler correctly. If there are any inconsistencies, the reasons can be immediately discovered and investigated, thus improving the accuracy of the interpreter.
  • Performance comparison: Although this code does not explicitly compare execution times, you can compare their performance somewhat indirectly by running both interpreters simultaneously and comparing the results. If one interpreter is always faster than the other, consider optimizing it.
  • Consistency: Even if the results of two interpreters are correct, there may be slight differences due to different implementations. By comparing these differences, you can ensure consistency in their implementation and avoid potential confusion and errors.

Overall, this comparison is an effective testing strategy to ensure the correctness and consistency of interpreters, while also allowing some degree of evaluation of their performance.

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/811142

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: [email protected]

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索