FIT2014 代写 Assignment 2

截止日期：2024年10月4日星期五晚上11:55

在这些练习中，你将： – 使用lex实现词法分析器（问题3）； – 使用lex和yacc实现解析器（问题1 – 6）； – 编程实现图灵机（问题7）； – 通过应用相关方法进行计算，了解量子电路和量子寄存器的一些方面（问题2 – 6）； – 练习与泵引理和上下文无关语言相关的技能（问题8）。

问题7的解决方案必须在模拟器Tuatara中实现。提供的版本是2.1，在Moodle的第8周可以找到，文件名是tuatara – monash – 2.1.jar。必须使用这个版本，而不是从互联网上下载的其他版本。不要解压此文件，必须直接使用Java运行时运行。

如何管理此作业

你应该现在就开始这项作业，并在截止日期之前合理分配时间。在第10周之前尽可能多地完成。
不要被这份文档的长度吓倒！其中大部分是一个扩展教程，帮助你开始使用lex和yacc（第7 – 11页）以及为你提供的用C编写的函数文档（第12 – 17页）；一些矩阵和示例输出也占用了相当多的空间。有一个关于量子计算一些基础知识的可选三页介绍（第17 – 19页），对于那些有兴趣了解更多的人来说是有用的，但不是本作业所必需的。虽然lex和yacc对你来说是新的，但关于它们的问题只要求你修改它们的一些现有输入文件，而不是从头开始编写自己的输入文件。
作业所需的任务在第3 – 6页。
- 对于问题1 – 5，请阅读第7 – 11页的背景材料。
- 对于问题2 – 6，还请阅读第12 – 17页的背景材料。
- 对于问题7，请阅读第21页的背景材料。
- 对于问题8，请阅读第22页的背景材料。

指令

指令与作业1大致相同，只是一些文件名发生了变化，现在每个问题都有自己的目录。要开始处理作业，请从Moodle下载工作台asgn2.zip。创建一个新的Ed工作区并上传此文件，让Ed自动解压它。编辑student – id文件以包含你的姓名和学生ID。参考实验0，以提醒如何执行这些任务。

打开一个终端并切换到asgn2目录。你会发现该目录中已经有另外四个文件：plus – times – power.l，plus – times – power.y，quant.h和prob6.awk。你不会直接修改这些文件；你将制作前两个文件的副本并修改副本，而quant.h和prob6.awk必须保持不变（尽管在其他目录中拥有它们的副本是可以的）。

你需要使用plus – times – power.l作为起点，为问题1、3、4和5构建新的lex文件，并为问题4和5从plus – times – power.y构建一个新的yacc文件。你的提交必须包括：
1. 编辑为包含你的姓名和学生ID的文件student – id；
1. 一个lex文件prob1.l，应该通过修改plus – times – power.l的副本获得；
1. 一个PDF文件prob2.pdf，应包含你对问题2的解决方案（开头包含你的姓名和学生ID）；
1. 一个lex文件prob3.l，也应该通过修改plus – times – power.l的副本获得；
1. 一个lex文件prob4.l，应该通过修改prob3.l的副本获得；
1. 一个yacc文件prob4.y，应该通过修改plus – times – power.y的副本获得；
1. 一个lex文件prob5.l，应该通过修改prob4.l的副本获得；
1. 一个yacc文件prob5.y，应该通过修改prob4.y的副本获得；
1. 一个文本文件prob6.txt，应包含十行，即你对问题6的解决方案；
1. 一个Tuatara图灵机文件prob7.tm；
1. 一个PDF文件prob8.pdf，应包含你对问题8的解决方案（开头包含你的姓名和学生ID）。

原始目录结构和文件位置必须保留。对于每个问题，你提交的文件必须在相应的子目录中，即问题x的文件在problemx子目录中。

每个这些问题子目录都包含具有所需文件名的空文件。这些文件必须分别被你编写的文件替换，如上文所述。在提交之前，请检查这些空文件中的每一个确实被你自己的文件替换。

要提交你的工作，请通过在文件管理器面板中单击“下载全部”将Ed工作区下载为zip文件。“下载全部”选项保留zip文件的目录结构，这有助于标记过程。你必须在上述给定的截止日期之前将此zip文件提交到Moodle。

作业任务
- 首先，阅读第7 – 11页关于“Lex，Yacc和PLUS – TIMES – POWER语言”的内容。
- 问题1. [2分] 构建prob1.l，如第9 – 11页所述，以便它可以与plus – times – power.y一起用于构建PLUS – TIMES – POWER的解析器。
- 现在参考“量子电路，寄存器和语言QUANT”文档，第12 – 17页。实际上，对于问题2，你可以只关注第15 – 17页和语言QCIRC。
- 问题2. [3分] 为语言QCIRC编写一个上下文无关文法，该语言基于{I，H，X，Y，Z，CNOT，TOF，*，⊗，(，)}这十一个符号的字母表。它可以是键入的或手写的，但必须是PDF格式并保存为文件prob2.pdf.pdf。
- 现在我们使用一些非常基本的正则表达式（在lex文件prob3.l中）和一个CFG（在yacc文件prob4.y中）为QCIRC构建一个词法分析器（问题3）和一个解析器（问题4）。
- 问题3. [3分] 使用为PLUS – TIMES – POWER提供的文件作为起点，构建一个lex文件prob3.l，并使用它为QCIRC构建一个词法分析器。你需要为各种标记引入简单的正则表达式，以及其他事情。示例输出：
- $./a.out
  CNOT* ( H (x)I)
  Token: CNOT; Lexeme: CNOT
  Token and Lexeme: *
  Token and Lexeme: (
  Token: H; Lexeme: H
  Token: KRONECKERPROD; Lexeme: (x)
  Token: I; Lexeme: I
  Token and Lexeme: )
  Token and Lexeme:
  Control – D
- 问题4. [6分] 制作prob3.l的副本，称为prob4.l，然后修改它以便可以与yacc一起使用。然后从plus – times – power.y构建一个yacc文件prob4.y。然后使用这些lex和yacc文件为QCIRC构建一个解析器，该解析器可以正确评估该语言中的任何表达式。请注意，你不必自己编程任何量子表达式函数。它们已经被编写：请参阅yacc文件的“程序”部分。你的yacc文件中的操作将需要调用这些函数，你可以使用plus – times – power.y中pow(…)的函数调用作为模板。你的任务核心是在yacc格式的规则部分中编写语法规则，并带有相关的操作，使用plus – times – power.y中的示例作为指导。你还需要在声明部分进行一些修改；请参阅第10页和以下进一步的细节。当将你的语法输入到prob4.y的规则部分时，最好保持现有非终结符start的规则不变，因为这有一些额外的东西旨在允许你在单独的行上输入一系列单独的表达式。因此，从你在问题2中的语法中获取起始符号，并将其表示为非终结符line，而不是start。你需要在声明部分进行的具体修改应该是：
  - 你需要为标记I，H，X，Y，Z，CNOT，TOF和KRONECKERPROD进行新的%token声明。这些与NUMBER标记的行具有相同的结构，除了“num”被替换为“str”（因为上述每个标记代表一个字符串，是矩阵，寄存器或操作的名称，而NUMBER代表一个数字）。
  - 你应该将我们的两个矩阵操作*（乘法）和KRONECKERPROD（克罗内克积，⊗）分别包含在%left或%right语句中。这样的语句指定操作是左结合还是右结合，即你是从左到右还是从右到左进行多个连续操作。在数学上，对于*和⊗，这并不重要。所以，对于这些，你可以使用%left或%right。但你应该这样做，因为它有助于解析器确定执行操作的顺序并消除一些歧义。对于%left或%right语句在不同行上的操作，具有更高行号的操作（即在文件中更晚）具有更高的优先级。普通矩阵乘法应该具有比克罗内克积更高的优先级。
  - 对于非终结符号，你可以包含一个%type行来声明其类型，即当评估从该非终结符生成的表达式时返回的值的类型。例如，%type start here。在这里，“qmx”是我们用于量子矩阵的类型名称。各种类型名称可以在文件中稍早的%union语句中看到。但是你不需要知道它是如何工作的来完成这项任务。
  - 你仍然应该使用start作为你的起始符号。如果你使用另一个名称代替，你将需要修改%start行。示例输出：
- $./a.out
  CNOT* ( H (x)I)
  4×4 matrix:
  0.7071 0.0000 0.7071 0.0000
  0.0000 0.7071 0.0000 0.7071
  0.0000 0.7071 0.0000 -0.7071
  0.7071 0.0000 -0.7071 0.0000
  Control – D
- 问题5. [5分] 制作prob4.l的副本，称为prob5.l。此外，制作prob4.y的副本，称为prob5.y。然后进一步修改这些lex和yacc文件，为QUANT构建一个解析器，该解析器可以正确评估该语言中的任何表达式。同样，你的任务核心是在prob5.y的yacc格式的规则部分中编写语法规则，并带有相关的操作。你还需要新的标记KET0和KET1，它们分别代表k0和k1。这些标记需要在prob5.l中有适当的规则，并在prob5.y中有声明，并且你将在语法中使用它们。
- 问题6. [5分] 在problem6目录中，你会找到一个文件prob6.awk。这是一个用于将你的学生ID号转换为特定量子寄存器表达式的awk程序。通过使用awk – f prob6.awk运行这个awk程序来进行此转换，然后（当它等待你的输入时）输入你的学生ID号。你将看到量子寄存器表达式作为输出出现。（a）复制这个量子寄存器表达式（它将是QUANT的成员）并将其作为文本文件prob6.txt的第一行输入。（b）对你来自（a）的表达式运行你的解析器，并通过将评估结果附加到文件prob6.txt来报告它。（a）的答案应该是你的文件prob6.txt的第一行。（b）的答案应该占据其余九行。因此，该文件应该总共有十行。你可以使用wc prob6.txt来验证这一点。例如，如果你的ID是12345678，那么你的十行文件prob6.txt应该如下所示：
- (X (x) Y (x) Z) * (Y (x) CNOT) * (X (x) Y (x) Z) * (k0 (x) k0 (x) k0)
  3 – qubit register, 8 – element vector:
  0.0000
  0.0000
  0.0000
  0.0000
  0.0000
  0.0000 + 1.0000i
  0.0000
  0.0000
- 图灵机 现在参考第21页上关于数字选择函数的描述。
- 问题7. [7分] 在Tuatarav2.1中构建一个计算数字选择函数的图灵机，并将图灵机保存为文件prob7.tm。
- 上下文无关语言 现在参考第22页上关于通用模型的描述。
- 问题8. [9分] （a）使用正则语言的泵引理证明，不存在通用正则表达式。（b）使用上下文无关语言的泵引理证明，不存在通用上下文无关文法。你的提交可以是键入的或手写的，但必须是PDF格式并保存为单个文件prob8.pdf。
Lex，Yacc和PLUS – TIMES – POWER语言在作业的这一部分，你将首先使用词法分析器生成器lex，然后与解析器生成器yacc一起使用。

一些关于Lex和Yacc的有用参考： – T. Niemann，Lex & Yacc Tutorial，http://epaperpress.com/lexandyacc/ – Doug Brown，John Levine，和Tony Mason，lex and yacc（第2版），O’Reilly，2012。 – lex和yacc的手册页。

我们将用一种基于简单算术表达式的语言PLUS – TIMES – POWER来说明这些程序的使用，该语言涉及非负整数，仅使用加法，乘法和幂运算。然后，你将在与量子计算相关的一些语言上使用lex和yacc。

PLUS – TIMES – POWER PLUS – TIMES – POWER语言由涉及加法，乘法和非负整数幂的表达式组成，没有任何括号（除了函数Power所需的括号）。示例表达式包括：

5 + 8，8 + 5，3 + 5 ∗ 2，13 + 8 ∗ 4 + Power(2，Power(3，2))，Power(1，3) + Power(5，3) + Power(3，3)，
Power(999，0)，0 + 99 ∗ 0 + 1，2014，10 ∗ 14 + 74 + 10 ∗ 13 ∗ 73，2 ∗ 3 ∗ 5 ∗ 7 ∗ 11 ∗ 13 ∗ 17 ∗ 19。

在这些表达式中，整数以无符号十进制编写，没有前导零或小数点（因此2014，86，10，7和0是可以的，但+2014， – 2014，86.0，A，007和00不是）。

对于词法分析，我们将每个非负整数视为标记NUMBER的词素。

Lex 按照惯例，输入到lex的文件的名称以.l结尾。这样的文件有三个部分： – 定义； – 规则； – C代码。

这些部分由双百分号%%分隔。注释以/*开始并以*/结束。当lex在文件上运行时，任何注释都将被忽略。

你会在本作业的文件中找到一个输入文件plus – times – power.l。现在研究它的结构，识别三个部分并注意到各种代码已被注释掉。这些代码目前还不需要，但稍后会需要一些。

我们主要关注文件中间的规则部分。它由一系列形式为pattern { action }的语句组成，其中pattern是一个正则表达式，action是用C编写的指令，指定对与模式匹配的文本执行的操作。在我们的文件