jrop编译

❶ 编译原理试题·

Lex和Yacc应用方法(一).初识Lex
草木瓜 20070301
Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler
编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分
析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，
入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看简单的例子(注：本文所有实例皆在RetHat linux下完成):
一个简单的Lex文件 exfirst.l 内容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下执行命令flex解析，会自动生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
进行编译生成parser可执行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll链结选项，cc编译时会出现以下错误，后面会进一步说明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

创建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通过已生成的可执行程序，进行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法会有个直观的了解：
1.定义Lex描述文件
2.通过lex，flex工具解析成lex.yy.c文件
3.使用cc编译lex.yy.c生成可执行程序

再来看一个比较完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
进行解析编译：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
这里就没有加-ll选项，但是可以编译通过。下面开始着重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的结构介绍
Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识
别程序，由该程序识别出输入文本中的各个单词。一般可以分为<定义部分><规则部
分><用户子程序部分>。其中规则部分是必须的，定义和用户子程序部分是任选的。

(1)定义部分
定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括include语句、声明语句
在内的C语句。这部分跟普通C程序开头没什么区别。
%{
#include "stdio.h"
int linenum;
%}
(2) 规则部分
规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和
动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组
成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单
词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多
行执行语句，也可以用{}括起来。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.规则部分的正则表达式
规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字
符含义：
A-Z, 0-9, a-z 构成模式部分的字符和数字。
- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。
\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义，
只取字符的本身。

[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字
符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一个。

^ 表示否定。
* 匹配0个或者多个上述模式。
+ 匹配1个或者多个上述模式。
? 匹配0个或1个上述模式。
$ 作为模式的最后一个字符时匹配一行的结尾。
{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可
能出现1次或3次。[a-z]{5} 表示长度为5的，由a-z组成的
字符。此外，还可以表示预定义的变量。

. 匹配任意字符，除了 \n。
( ) 将一系列常规表达式分组。如：{Letter}({Letter}|{Digit})*
| 表达式间的逻辑或。
"一些符号" 字符的字面含义。元字符具有。如："*" 相当于 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式，
只匹配模版中"/"前面的部分。如：模式为 ABC/D 输入 ABCD，
时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话，
ABCE就不会去匹配ABC/D。

B.规则部分的优先级

规则部分具有优先级的概念，先举个简单的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此时，如果输入内容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符
时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现
"AAAA"只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符
匹配规则。
如果将规则
AAAA {printf("THREE\n");};
改为
AAAAA {printf("THREE\n");};
./parser < file1.txt 输出结果为：
THREE
TWO

再来一个特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
并输入title，Lex解析完后发现，仍然存在两个规则，这时Lex只会选择第一个规则，下面
的则被忽略的。这里就体现了Lex的顺序优先级。把这个例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex编译时会提示：warning, rule cannot be matched.这时处理title字符时，匹配
到第一个规则后，第二个规则就无效了。
再把刚才第一个例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 显示效果是一样的，最后一项规则肯定是会忽略掉的。

C.规则部分的使用变量
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分
别代指特定的含义，在两个%%之间，可以通过{int}{float}进行直接引用，简化模
式定义。

(3) 用户子程序部分
最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子
程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，
当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的内部变量和函数
内部预定义变量：
yytext char * 当前匹配的字符串
yyleng int 当前匹配的字符串长度
yyin FILE * lex当前的解析文件，默认为标准输出
yyout FILE * lex解析后的输出文件，默认为标准输入
yylineno int 当前的行数信息
内部预定义宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的
默认动作

内部预定义的函数：
int yylex(void) 调用Lex进行词法分析
int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解
析。 因此它可以用来解析多个文件。代码可以写在第三段，这
样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的
文件，直到所有的文件都被解析。最后，yywrap() 可以返回1
来表示解析的结束。

lex和flex都是解析Lex文件的工具，用法相近，flex意为fast lexical analyzer generator。
可以看成lex的升级版本。

相关更多内容就需要参考flex的man手册了，十分详尽。

四.关于Lex的一些综述
Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，
并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，
它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的
结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了。

❷ 为啥自已编译的op固件运行中断 V21.02

固体运行没有编译正确。
op并且附带3000左右的软件包，用户可以方便的自定义功能来制作固件。也可以方便的移植各类功能到openwrt下。
op固件是，经济金融，企业管理，法律法规，社会民生，科学教育，健康生活，体育运动，文化艺术，电子数码，电脑网络，娱乐休闲，行政地区，心理分析，医疗卫生，精选，知道专栏，知道日报，知道的大数据。

❸ 开篇：XLA是什么

XLA (Accelerated Linear Algebra)是专用于机器学习的编译器，机器学习的运算中99%都是向量乘以矩阵、矩阵乘以矩阵的计算，XLA是专门用来优化这些计算的。

举个例子，运行在GPU上的 model_fn 函数会顺序调用 multiply 、 add 和 rece_sum 这三个op，而且 multiply ，也就是 y * z 的计算结果会先从GPU拷贝回host，再拷贝到device作为 add 的input，同样的，add的计算结果也会以相同的方式传递给下一个op。

显然，对于整个函数来说，将中间变量在host和device间来回倒腾是没有意义的。因此，如果把函数看作一个op，那在计算中产生的中间结果就不必返回到host，少了数据传输的时间开销，就可以大幅提升运算效率。

这种将多个op融合成一个op的方法就称为 fuse ，当前fuse的技术路线有：

XLA的优化当然不只是fuse，还有对计算图的优化，包括删除无效指令、减少内存占用、替换复杂指令等优化。下图是官方提供的性能报告，经XLA优化过后，Tensorflow BERT MLPerf的训练性能提升了~7倍。除了Tensorflow外，XLA还支持 JAX 、 Julia 、 PyTorch 和 Nx 等前端。

jit 是指在首次运行时将函数编译成二进制程序，后续再调用该函数时直接运行先前编译好的程序而非python code。 @tf.funciton 修饰的函数（包括它的子函数）会做 jit 。除非signature发生了变化，也就是input的shape或dtype和编译时不同，否则 get_MSE 是不需要重复编译的。

@tf.function 将函数内的ops替换成一组（ XlaCompile , XlaRun ) ops，在运行时前者负责编译，并将编译结果-- executable 保存到cache，后者负责运行executable。如果cache里已经有编译好的程序就不需要编译了，例如 get_MSE(tf.constant(3.0), tf.constant(4.0)) 。

XLA编译器支持的语言（IR）是HLO（High Level Operations），顾名思义这些语言是由一个个op组成，因此，我们在编译前需要先从python code中提取出所有ops，再将它们转换成HLO。

JAX通过tracing的方式，从 @jax.jit 修饰的函数中提取ops，这些ops通过 jaxpr 来表示。然后再通过XLA client提供的API为ops生成相应的HLO。PyTorch/XLA也是采用类似的方法来生成HLO。

Tensorflow的 tf2xla 为每个 Op 创建了一个同名的 XlaOp 用于生成HLO， XlaOp 派生于 Op ，使用相同的注册机制，因此，只要把要编译的子图根据拓扑排序运行一遍就能生成它的HLO。

HLO先经过一系列 pass 优化后再将HLO lowering成ISA，最后将编译好的二进制封装到 executable 。

除了二进制程序，它还包含运行该程序所需要的infos和options。调用 executable.run() 就可以执行计算图。

❹ 求C语言文法及产生式！要做C编译器——语法分析部分

转自http://blog.csdn.net/rill_zhen/article/details/7701259http://blog.csdn.net/rill_zhen/article/details/7701259
希望能帮到你

编译原理-1-C语言的文法
编译原理-1-C语言的文法
c语言的文法产生式：
program ->
external_declaration
| program external_declaration
external_declaration ->
function_definition
| declaration
function_definition -> type_specifier declarator compound_statement
type_specifier ->
VOID
| CHAR
| INT
| FLOAT
declarator
pointer direct_declarator
| direct_declarator
Pointer->
'*'
| '*' pointer
direct_declarator
IDENTIFIER
|direct_declarator’[‘ ‘]’
|direct_declarator ’[’ constant_expression ’]’
| IDENTIFIER '(' parameter_list ')'
| IDENTIFIER '(' ')'
|direct_declarator‘,’identifier_list
identifier_list
: IDENTIFIER
| identifier_list ',' IDENTIFIER
constant_expression->
conditional_expression
parameter_list ->
parameter_declaration
| parameter_list ',' parameter_declaration

parameter_declaration ->
declaration_specifiers IDENTIFIER
compound_statement ->
'{' '}'
| '{' statement_list '}'
| '{' declaration_list statement_list '}'
declaration_list ->
declaration
| declaration_list declaration
Declaration->
init_declarator
| init_declarator_list ',' init_declarator
init_declarator ->
declarator
| declarator '=' initializer
Initializer ->
assignment_expression
| '{' initializer_list '}'
| '{' initializer_list ',' '}'
initializer_list ->
initializer
| initializer_list ',' initializer
statement_list->
statement
| statement_list statement
Statement ->
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
expression_statement ->
';'
| expression ';'
selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
iteration_statement->
WHILE '(' expression ')' statement
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
jump_statement
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
expression
: assignment_expression
| expression ',' assignment_expression
assignment_expression ->
conditional_expression
| unary_expression assignment_operator assignment_expression
conditional_expression ->
logical_or_expression
| logical_or_expression ' ' expression ':' conditional_expression
logical_or_expression ->
logical_and_expression
| logical_or_expression OR_OP logical_and_expression
logical_and_expression
: inclusive_or_expression
| logical_and_expression AND_OP inclusive_or_expression
inclusive_or_expression->
exclusive_or_expression
| inclusive_or_expression '|' exclusive_or_expression
exclusive_or_expression
: and_expression
| exclusive_or_expression '^' and_expression
and_expression
: equality_expression
| and_expression '&' equality_expression
equality_expression
: relational_expression
| equality_expression EQ_OP relational_expression
| equality_expression NE_OP relational_expression
relational_expression
: shift_expression
| relational_expression '$amp;
| relational_expression '$amp;>apos;$ shift_expression
| relational_expression LE_OP shift_expression
| relational_expression GE_OP shift_expression
shift_expression
: additive_expression
| shift_expression LEFT_OP additive_expression
| shift_expression RIGHT_OP additive_expression
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
cast_expression
: unary_expression
| '(' type_name ')' cast_expression
unary_expression
: postfix_expression
| INC_OP unary_expression
| DEC_OP unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
postfix_expression ->
: primary_expression
| postfix_expression '[' expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER
| postfix_expression PTR_OP IDENTIFIER
| postfix_expression INC_OP
| postfix_expression DEC_OP
primary_expression ->
IDENTIFIER
| CONSTANT
| STRING_LITERAL
| '(' expression ')'
argument_expression_list
: assignment_expression
| argument_expression_list ',' assignment_expression
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
assignment_operator ->
'='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
storage_class_specifier ->
TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
struct_or_union_specifier
: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
| struct_or_union '{' struct_declaration_list '}'
| struct_or_union IDENTIFIER
struct_or_union
: STRUCT
| UNION
struct_declaration_list
: struct_declaration
| struct_declaration_list struct_declaration
struct_declaration
: specifier_qualifier_list struct_declarator_list ';'
specifier_qualifier_list ->
type_specifier specifier_qualifier_list
| type_specifier
| type_qualifier specifier_qualifier_list
| type_qualifier
struct_declarator_list ->
struct_declarator
| struct_declarator_list ',' struct_declarator
struct_declarator ->
: declarator
| ':' constant_expression
| declarator ':' constant_expression
enum_specifier ->
ENUM '{' enumerator_list '}'
| ENUM IDENTIFIER '{' enumerator_list '}'
| ENUM IDENTIFIER
enumerator_list ->
enumerator
| enumerator_list ',' enumerator
Enumerator ->
IDENTIFIER
| IDENTIFIER '=' constant_expression
type_qualifier ->
CONST
| VOLATILE
type_qualifier_list ->
type_qualifier
| type_qualifier_list type_qualifier
parameter_type_list ->
parameter_list
| parameter_list ',' ELLIPSIS
parameter_list ->
: parameter_declaration
| parameter_list ',' parameter_declaration
type_name ->
specifier_qualifier_list
| specifier_qualifier_list abstract_declarator
abstract_declarator ->
pointer
| direct_abstract_declarator
| pointer direct_abstract_declarator
direct_abstract_declarator ->
'(' abstract_declarator ')'
| '[' ']'
| '[' constant_expression ']'
| direct_abstract_declarator '[' ']'
| direct_abstract_declarator '[' constant_expression ']'
| '(' ')'
| '(' parameter_type_list ')'
| direct_abstract_declarator '(' ')'
| direct_abstract_declarator '(' parameter_type_list ')'
labeled_statement ->
IDENTIFIER ':' statement
| CASE constant_expression ':' statement
| DEFAULT ':' statement

❺ 求教，在编译环境里，op的wifi配置文件在哪个路径

不建议修改源码，还是新建一个files目录，然后新增一个files/etc/config/wireless文件，编译的时候会自动打包目录

❻ 怎么用C++编译一个简单的计算器

我借鉴了别人的某计算器，因为你没有说多简易...我就找了个差不多的...
/*
程序名称:表达式计算器
编译环境:Microsoft Visual C++ 6.0
作者:吉林大学 计算机科学与技术学院 2006 罗泗勇
时间:200801
*/

/*
说明:
采用树形结构处理表达式,按优先级运算结果,一个加,减,乘,除或数值为一个节点
优先级如下:
函数:4
括号:3
乘除:2
加减:1
*/

#include <windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;

const char NUM[]={'0','1','2','3','4','5','6','7','8','9','.'};
const char OPERATION[]={'+','-','*','/'};
const double PI=3.14159265358979;
const double EE=2.71828182818281;

class Fun //处理系统数学函数的类
{
public:
Fun(string o,int t,double l=0.0,double r=0.0):op(o),type(t),lvalue(l),rvalue(r){}
static string FUN[];
double calc();
private:
int type; //666 0 1 sin90 2 3! 3 3C2
string op; //函数类型
double lvalue; //函数左边的值
double rvalue; //函数右边的值
static int FunNum;
};

int Fun::FunNum=8;
string Fun::FUN[]={"!","sin","cos","tan","log","ln","C","A","^"};
/*
函数说明:
1:log是以10为底的工程对数
2:ln 是以e为底的自然对数
3:C 计算组合数 输入规则 如计算 3取2的组合 输入表达式 3C2
4:A 计算排列数 输入规则 如计算 3取2的排列 输入表达式 3A2
5:! 计算阶乘
6:^ x的y次方 输入 x^y
*/

int factorial(int n) //阶乘函数
{
int i,s=1;
for(i=1;i<=n;i++)
s*=i;
return s;
}

int C(int a,int b)
{
return factorial(a)/(factorial(b)*factorial(a-b));
}

int A(int a,int b)
{
return factorial(a)/factorial(b);
}

double Fun::calc() //计算系统函数的值
{
if(type==0)
return lvalue;
else
{
if(op=="!")
return factorial(lvalue);
if(op=="sin")
return sin(rvalue/180*PI);
if(op=="cos")
return cos(rvalue/180*PI);
if(op=="tan")
return tan(rvalue/180*PI);
if(op=="log")
return log10(rvalue);
if(op=="ln")
return log10(rvalue)/log10(EE);
if(op=="C")
return C(lvalue,rvalue);
if(op=="A")
return A(lvalue,rvalue);
if(op=="^")
return pow(lvalue,rvalue);
else
{
string err="暂时没有函数"+op;
MessageBox(NULL,err.c_str(),"错误",MB_OK);
return 0;
}
}
}

struct Unit //双向链表保存运算单元
{
Unit(int p,char o,string c,double v,int t,Unit * pr=NULL,Unit * n=NULL)
:PRI(p),Operation(o),Code(c),value(v),Type(t),Pre(pr),Next(n){}
int PRI; //优先级

char Operation; //操作符
string Code; //原始代码
double value; //数据

int Type; //类型 操作符0 数据1 函数2
Unit * Pre; //构成双向链表
Unit * Next;
};

class Node //表达式树状结构的节点
{
public:
Node(char o,int p,int e=1,double v=0,Node * ph=NULL,Node * pl=NULL,Node * pr=NULL)
:Operation(o),PRI(p),Expression(e),value(v),Head(ph),Left(pl),Right(pr){}
Node * Head; //节点的根,左树枝,右树枝
Node * Left;
Node * Right;
double GetValue();
char GetOperation() const {return Operation;}
int GetPri() const {return PRI;}
int IsExp() const {return Expression;}
private:
char Operation; //操作符
int PRI; //优先级
int Expression; //记录该节点是否是表达式0 1
double value; //该节点的值
};

double Node::GetValue() //运算该节点的值
{
if(IsExp()) //该节点的值还未算出来
{
double lvalue,rvalue;
lvalue=Left->GetValue();
rvalue=Right->GetValue();
Expression=0;
char op=GetOperation();
switch(op)
{
case '+':
return lvalue+rvalue;
case '-':
return lvalue-rvalue;
case '*':
return lvalue*rvalue;
case '/':
return lvalue/rvalue;
default:
return 0;
}
}
else
return value;
}

bool Isnum(char c)
{
for(int i=0;i<sizeof(NUM);i++)
{
if(c==NUM[i])
return true;
}
return false;
}

bool Isoperation(char c)
{
for(int i=0;i<sizeof(OPERATION);i++)
{
if(c==OPERATION[i])
return true;
}
return false;
}

Unit * Analyse(string exp) //分析表达式并生成链表
{
int pri=0; //当前优先级
int stat=-1; //当前的读入状态 括号 0 数据 1 运算符 2
Unit * head=NULL,* p=NULL;
int i=0,explen;
explen=exp.size();
for(i=0;i<explen;i++)
{
char c=exp.at(i);
if(c=='(')
{
pri+=3;
stat=0;
}
else if(c==')')
{
pri-=3;
stat=0;
}
else if(Isoperation(c)) //操作符不会出现在表达式开头
{
Unit * temp=p;
int add_pri; //自身增加的优先级
if(c=='+' || c=='-')
add_pri=1;
else
add_pri=2;
p->Next=new Unit(pri+add_pri,c," ",0,0);
p=p->Next;
p->Pre=temp;
}
else //其他的当做函数处理
{
string function="";
while(i<explen && (c=exp.at(i),! Isoperation(c)) && c!=')')
{
function+=c;
i++;
}
i--;

if(head==NULL)
{
p=new Unit(pri,' ',function,0,2);
head=p;
}
else
{
Unit * temp=p;
p->Next=new Unit(pri,' ',function,0,2);
p=p->Next;
p->Pre=temp;
}
}
}
return head;
}

Unit * Calc(Unit * head) //计算双向链表基本单元的值
{
Unit * p=head;
while(p!=NULL)
{
if(p->Type!=0) //非操作符
{
string temp=p->Code;
string op;
double lvalue=0,rvalue=0;
int l_point=0,r_point=0;
int i=0,type=0;
char ch;
while(i<temp.size() && (ch=temp.at(i),Isnum(ch)))
{
if(ch=='.')
{
l_point++;
i++;
continue;
}
if(! l_point)
lvalue*=10;
lvalue+=(ch-'0')*pow(10,-l_point);
i++;
if(l_point)
l_point++;
}
while(i<temp.size() && (ch=temp.at(i),! Isnum(ch)))
{
op+=ch;
type=1;
i++;
}
while(i<temp.size() && (ch=temp.at(i),Isnum(ch)))
{
if(ch=='.')
{
r_point++;
i++;
continue;
}
if(! r_point)
rvalue*=10;
rvalue+=(ch-'0')*pow(10,-r_point);
i++;
if(r_point)
r_point++;
}
Fun * f=new Fun(op,type,lvalue,rvalue);
p->value=f->calc();
}
p=p->Next;
}
return head;
}

Node * Tree(Unit * head) //生成表达式树
{
Node * root=NULL,* proot=NULL,* pbranch=NULL;
Unit * p=head;
int now_pri; //当前优先级
bool hadop=false;
while(p!=NULL)
{
if(p->Type==0) //如果是一个操作符
{
hadop=true;
if(root==NULL)
{
proot=new Node(p->Operation,p->PRI,1);
root=proot;
pbranch=root;
now_pri=p->PRI;
proot->Left=new Node(' ',0,0,p->Pre->value);
proot->Right=new Node(' ',0,0,p->Next->value);
}
else
{
if(p->PRI<=now_pri) //优先级低于当前优先级,树根方向 //最初写的 if(p->PRI<now_pri),9/3/3=9,错的
{
proot=new Node(p->Operation,p->PRI,1); //新的树根
proot->Left=root; //根的变换
proot->Right=new Node(' ',0,0,p->Next->value);
root=proot;

pbranch=proot; //右树枝的变换
//pbranch->Right=new Node(' ',0,0,p->Pre->value); //树枝右边取值
}
else
{
Node * temp;
temp=new Node(p->Operation,p->PRI,1);

pbranch->Right=temp;
temp->Head=pbranch;

pbranch=pbranch->Right;
pbranch->Left=new Node(' ',0,0,p->Pre->value);
pbranch->Right=new Node(' ',0,0,p->Next->value);
}
now_pri=p->PRI;
}
}
p=p->Next;
}
if(! hadop)
root=new Node(' ',0,0,head->value);
return root;
}

int main()
{
string exp;

//ifstream infile("test.txt",ios::in);
while(! getline(cin,exp).eof())
{
if(exp=="")
continue;
Unit * h=Analyse(exp);
h=Calc(h);
Node * root=Tree(h);
cout<<exp<<"="<<root->GetValue()<<endl;
}
return 0;
}

❼ 编译原理 四元式

四元式是一种比较普遍采用的中间代码形式。

代码段的四元式表达式：

101 T:=0 （表达式为假的出口）

103 T:=1 （表达式为真的出口）

因为用户的表达式只有一个A<B，因此A<B的真假出口就是表达式的真假出口，所以

100: if a<b goto 103 （a<b为真，跳到真出口103）

101: T:=0（否则，进入假出口）

102: goto 104 （要跳过真出口，否则T的值不就又进入真出口了，为真）

103: T:=1

104:（程序继续执行）

(7)jrop编译扩展阅读：

四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。

四元式实际上是一种“三地址语句”的等价表示。它的一般形式为：

(op,arg1,arg2,result)

其中， op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：

result ∶= arg1 op arg2

需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列

T1∶=B*C

T2∶=A+T1

其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符 (如无条件转移)时，arg2甚至arg1应缺省，即result∶=op arg1或 op result ；对应的一般形式为：

(op,arg1,,result)

或

(op,,,result)

❽ JIT（上）：Tensorflow如何实现即时编译

Tensorflow的JIT（just-in-time）是指在运行 @tf.function 修饰的python函数时，由 jit 、 tf2xla 和 XLA 一起完成一系列如子图构造、子图优化、图编译和图执行等操作。编译后的可执行程序-- executable 会存放到cache中，供再次调用时直接获取执行。JIT的好处在 开篇 已经讲过了，这里不再赘述。

JIT的流程可以概括为：Tensorflow子图构造/优化，graph -> HLO，编译/执行，合并计算结果到Tensorflow图这四部分。本文只涉及图编译和图执行。

函数中ops在子图构造阶段被包裹进一个cluster node，并替换成 xla_compile 和 xla_run 这两op，而 XlaCompileOp 和 XlaRunOp 就是它们的 OpKernel ，分别用于图编译和执行。

XlaCompileOp通过 XlaCompilationCache 获取或编译executable，并将其封装成 XlaExecutableClosure ，并缓存在 XlaExecutableClosureStore 。 XlaRunOp 用从XlaCompileOp传递来的key在cache中查找并执行executable。

从编译流程图可以看到，XLA的编译结果会缓存到XlaCompilationCache，后续调用可以根据 signature 在cache中查找executable。

函数的 signature 是由 BuildSignature(function, args) 根据函数和arguments生成的。即使是同一个函数，只要input tensors不同，signature也会不一样，这就是 power() 被编译两次的原因：第三次函数调用时，由于无法通过signature在cache中找到executable而触发编译。

signature表示唯一的计算图：只要函数中的ops序列和arguments（type/shape）是确定的，那么计算图也是确定的。

编译之前需要通过 tf2xla 将图转换成XLA支持的语言 HLO 。tf2xla为每个Tensorflow op创建了生成HLO的 XlaOp ，因此，只要执行该Tensorflow子图，就可以生成具有相同的拓扑排序的HLO -- XlaComputation 。

XlaComputation （HLO）可以认为是一个运行在device上的纯函数，它的input/output会伴随着host-to-device（H2D）和device-to-host（D2H）的数据传输。

我们知道，Tensorflow图中的input tensor有两种： tf.Placeholder 和 tf.Variable ，前者每个step都会将新data发送到device，而后者是模型参数，它们会常驻内存，只在store/load checkpoint才会有H2D/D2H。

而纯函数的定义是：

不管是input还是output，虽然variable和其他argument一样存在于HLO的参数列表和返回值列表中，但它们实际上是常驻于device的，不需要也不应该H2D/D2H。

因此，HLO在编译时还需要通过 argument_input_indices 、 resource_input_indices 和 resource_update_to_input_index 等options来区分arguments和variables。

此外，如果有input是常数，为了避免无谓的H2D开销，可以把它固化到函数内部。同理，对于常数output，它没必要出现在函数中，可以直接定义在 XlaCompilationResult 的output buffer。

XlaCompilationResult是 Graph -> HLO 的output，它封装了HLO以及上述部分metadata、buffers。

XlaCompileOp会把编译好的executable、metadata、input/output buffers、options等统统封装进一个closure -- XlaExecutableClosure ，并将其缓存在 XlaExecutableClosureStore 供 XlaRunOp 获取。

XlaRunOp 可以通过一个数字字符串key（从0开始累加）从cache中查找并执行XlaExecutableClosure，这个key由XlaCompileOp提供。

❾ 有人知道编译原理实验之词法分析器用C++怎么做吗

#include "globals.h"
#include "util.h"
#include "scan.h"
#include "parse.h"

static TokenType token; /* holds current token */

/* function prototypes for recursive calls */
static TreeNode * stmt_sequence(void);
static TreeNode * statement(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * exp(void);
static TreeNode * simple_exp(void);
static TreeNode * term(void);
static TreeNode * factor(void);

static void syntaxError(char * message)
{ fprintf(listing,"\n>>> ");
fprintf(listing,"Syntax error at line %d: %s",lineno,message);
Error = TRUE;
}

static void match(TokenType expected)
{ if (token == expected) token = getToken();
else {
syntaxError("unexpected token -> ");
printToken(token,tokenString);
fprintf(listing," ");
}
}

TreeNode * stmt_sequence(void)
{ TreeNode * t = statement();
TreeNode * p = t;
while ((token!=ENDFILE) && (token!=END) &&
(token!=ELSE) && (token!=UNTIL))
{ TreeNode * q;
match(SEMI);
q = statement();
if (q!=NULL) {
if (t==NULL) t = p = q;
else /* now p cannot be NULL either */
{ p->sibling = q;
p = q;
}
}
}
return t;
}

TreeNode * statement(void)
{ TreeNode * t = NULL;
switch (token) {
case IF : t = if_stmt(); break;
case REPEAT : t = repeat_stmt(); break;
case ID : t = assign_stmt(); break;
case READ : t = read_stmt(); break;
case WRITE : t = write_stmt(); break;
default : syntaxError("unexpected token -> ");
printToken(token,tokenString);
token = getToken();
break;
} /* end case */
return t;
}

TreeNode * if_stmt(void)
{ TreeNode * t = newStmtNode(IfK);
match(IF);
if (t!=NULL) t->child[0] = exp();
match(THEN);
if (t!=NULL) t->child[1] = stmt_sequence();
if (token==ELSE) {
match(ELSE);
if (t!=NULL) t->child[2] = stmt_sequence();
}
match(END);
return t;
}

TreeNode * repeat_stmt(void)
{ TreeNode * t = newStmtNode(RepeatK);
match(REPEAT);
if (t!=NULL) t->child[0] = stmt_sequence();
match(UNTIL);
if (t!=NULL) t->child[1] = exp();
return t;
}

TreeNode * assign_stmt(void)
{ TreeNode * t = newStmtNode(AssignK);
if ((t!=NULL) && (token==ID))
t->attr.name = String(tokenString);
match(ID);
match(ASSIGN);
if (t!=NULL) t->child[0] = exp();
return t;
}

TreeNode * read_stmt(void)
{ TreeNode * t = newStmtNode(ReadK);
match(READ);
if ((t!=NULL) && (token==ID))
t->attr.name = String(tokenString);
match(ID);
return t;
}

TreeNode * write_stmt(void)
{ TreeNode * t = newStmtNode(WriteK);
match(WRITE);
if (t!=NULL) t->child[0] = exp();
return t;
}

TreeNode * exp(void)
{ TreeNode * t = simple_exp();
if ((token==LT)||(token==EQ)) {
TreeNode * p = newExpNode(OpK);
if (p!=NULL) {
p->child[0] = t;
p->attr.op = token;
t = p;
}
match(token);
if (t!=NULL)
t->child[1] = simple_exp();
}
return t;
}

TreeNode * simple_exp(void)
{ TreeNode * t = term();
while ((token==PLUS)||(token==MINUS))
{ TreeNode * p = newExpNode(OpK);
if (p!=NULL) {
p->child[0] = t;
p->attr.op = token;
t = p;
match(token);
t->child[1] = term();
}
}
return t;
}

TreeNode * term(void)
{ TreeNode * t = factor();
while ((token==TIMES)||(token==OVER))
{ TreeNode * p = newExpNode(OpK);
if (p!=NULL) {
p->child[0] = t;
p->attr.op = token;
t = p;
match(token);
p->child[1] = factor();
}
}
return t;
}

TreeNode * factor(void)
{ TreeNode * t = NULL;
switch (token) {
case NUM :
t = newExpNode(ConstK);
if ((t!=NULL) && (token==NUM))
t->attr.val = atoi(tokenString);
match(NUM);
break;
case ID :
t = newExpNode(IdK);
if ((t!=NULL) && (token==ID))
t->attr.name = String(tokenString);
match(ID);
break;
case LPAREN :
match(LPAREN);
t = exp();
match(RPAREN);
break;
default:
syntaxError("unexpected token -> ");
printToken(token,tokenString);
token = getToken();
break;
}
return t;
}

/****************************************/
/* the primary function of the parser */
/****************************************/
/* Function parse returns the newly
* constructed syntax tree
*/
TreeNode * parse(void)
{ TreeNode * t;
token = getToken();
t = stmt_sequence();
if (token!=ENDFILE)
syntaxError("Code ends before file\n");
return t;
}
上面是一个语法分析器的主代码部分它可以识别类似下面的代码，但是由于篇幅有限，上面的代码不是完整代码，完整代码太长，还有好几个文件。
read x; { input an integer }
if 0 < x then { don't compute if x <= 0 }
fact := 1;
repeat
fact := fact * x;
x := x - 1
until x = 0;
write fact { output factorial of x }
end