lr(0)分析程序c语言,C语言编写源程序建立LR(1)分析器

时间: 2023-11-27 21:52:30 浏览: 31
以下是一个简单的 LR(0) 分析程序的 C 语言代码示例: ``` #include <stdio.h> #include <string.h> #include <ctype.h> #define MAX_RULES 100 #define MAX_SYMBOLS 100 #define MAX_STATES 100 int num_rules = 0; char rules[MAX_RULES][MAX_SYMBOLS]; char lhs[MAX_RULES]; int rhs_len[MAX_RULES]; char *rhs[MAX_RULES][MAX_SYMBOLS]; int num_symbols = 0; char symbols[MAX_SYMBOLS]; int num_states = 0; int goto_table[MAX_STATES][MAX_SYMBOLS]; int action_table[MAX_STATES][MAX_SYMBOLS]; int state_stack[MAX_STATES]; int symbol_stack[MAX_STATES]; int top = 0; int get_symbol_index(char symbol) { int i; for (i = 0; i < num_symbols; i++) { if (symbols[i] == symbol) { return i; } } symbols[num_symbols++] = symbol; return num_symbols - 1; } void add_rule(char *rule) { char *p = rule; int i; while (isupper(*p)) { p++; } lhs[num_rules] = *(p - 1); rhs_len[num_rules] = strlen(p); for (i = 0; i < rhs_len[num_rules]; i++) { if (isupper(p[i])) { rhs[num_rules][i] = malloc(sizeof(char)); *rhs[num_rules][i] = p[i]; } else { rhs[num_rules][i] = malloc(sizeof(char)); *rhs[num_rules][i] = get_symbol_index(p[i]); } } num_rules++; } void add_state(int *state) { int i; for (i = 0; i < num_states; i++) { if (memcmp(goto_table[i], state, num_symbols * sizeof(int)) == 0) { return; } } memcpy(goto_table[num_states], state, num_symbols * sizeof(int)); num_states++; } void closure(int *state) { int i, j, k, l; int changed = 1; while (changed) { changed = 0; for (i = 0; i < num_rules; i++) { for (j = 0; j < rhs_len[i]; j++) { if (isupper(*rhs[i][j])) { for (k = 0; k < num_rules; k++) { if (lhs[k] == *rhs[i][j]) { int match = 1; for (l = 0; l < j; l++) { if (state[l] != *rhs[i][l]) { match = 0; break; } } if (match) { if (!state[j]) { state[j] = -1; changed = 1; } } } } } } } } } void goto_state(int *state, int symbol, int *new_state) { int i; memcpy(new_state, state, num_symbols * sizeof(int)); for (i = 0; i < num_rules; i++) { if (*rhs[i][0] == symbol) { new_state[0] = i + 1; closure(new_state); add_state(new_state); } } } void build_lr0_automaton() { int i, j; int initial_state[MAX_SYMBOLS] = {1}; add_state(initial_state); closure(initial_state); for (i = 0; i < num_states; i++) { for (j = 0; j < num_symbols; j++) { if (isupper(symbols[j])) { int new_state[MAX_SYMBOLS] = {0}; goto_state(goto_table[i], symbols[j], new_state); if (new_state[0]) { if (symbols[j] == 'S') { action_table[i][j] = 'A'; } else { goto_table[i][j] = num_states; } } } } for (j = 0; j < num_rules; j++) { if (goto_table[i][lhs[j] - 'A']) { action_table[i][lhs[j] - 'A'] = j + 1; } } } } int main() { char rule[MAX_SYMBOLS]; int i, j; printf("Enter the rules (one per line, blank line to end):\n"); while (fgets(rule, MAX_SYMBOLS, stdin) && rule[0] != '\n') { add_rule(rule); } build_lr0_automaton(); printf("\nLR(0) automaton:\n"); printf(" States:"); for (i = 0; i < num_states; i++) { printf(" %d", i); } printf("\n Symbols:"); for (i = 0; i < num_symbols; i++) { printf(" %c", symbols[i]); } printf("\n Goto table:\n"); for (i = 0; i < num_states; i++) { printf(" %d:", i); for (j = 0; j < num_symbols; j++) { printf(" %d", goto_table[i][j]); } printf("\n"); } printf(" Action table:\n"); for (i = 0; i < num_states; i++) { printf(" %d:", i); for (j = 0; j < num_symbols; j++) { if (isupper(symbols[j])) { if (action_table[i][j]) { printf(" %c%d", action_table[i][j] == 'A' ? 'A' : 'S', action_table[i][j] - 1); } else { printf(" "); } } else { printf(" "); } } printf("\n"); } return 0; } ``` 如果您想要建立 LR(1) 分析器,可以使用 Lex 和 Yacc 工具来生成 C 语言代码。以下是一个简单的示例: Lex 文件(lexer.l): ``` %{ #include "y.tab.h" %} %% [ \t\n]+ ; [0-9]+ { yylval = atoi(yytext); return NUMBER; } [-+*/] { return yytext[0]; } . ; %% Yacc 文件(parser.y): ``` %{ #include <stdio.h> int yylex(); int yyerror(char *); %} %token NUMBER %left '+' '-' %left '*' '/' %right UMINUS %% program: /* empty */ | program statement '\n' ; statement: expression { printf("%d\n", $1); } ; expression: NUMBER | expression '+' expression { $$ = $1 + $3; } | expression '-' expression { $$ = $1 - $3; } | expression '*' expression { $$ = $1 * $3; } | expression '/' expression { $$ = $1 / $3; } | '-' expression %prec UMINUS { $$ = -$2; } ; %% int main() { yyparse(); return 0; } 然后使用以下命令生成分析器: ``` lex lexer.l yacc -d parser.y gcc lex.yy.c y.tab.c -o parser ``` 这将生成一个名为 parser 的可执行文件,可以使用以下命令运行它: ``` ./parser ``` 您可以输入简单的算术表达式,并在按下 Enter 键后看到计算结果。

相关推荐

最新推荐

recommend-type

词法分析示例程序(C语言编写,针对PL/0语言)

这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。 PL/0...
recommend-type

表驱动LL(1)语法分析程序.docx

(1)根据LL(1)分析法编写一个语法分析程序,输入文法的FIRST(α)和FOLLOW(U)集,由程序自动生成文法的预测分析表。 (2)所开发的程序可适用于不同的文法和任意输入串,且能判断该文法是否为LL(1)文法。 (3)对输入的...
recommend-type

4 实验四:LR分析程序的设计与实现

1、了解LR(0)分析方法是严格的从左向右扫描,和自底向上的语法分析方法。 2、掌握LR(0)语法分析方法。
recommend-type

编译原理实验一——C 语言词法分析器设计与实现

通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
recommend-type

C语言程序设计实现学生成绩记录簿

1)C语言课程设计的主要目的是培养学生综合运用C语言程序设计课程所学到的知识,编写C程序解决实际问题的能力,以及严谨的工作态度和良好的程序设计习惯。 2)通过课程设计的训练,学生应该能够了解程序设计的基本...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

用Spring boot和vue写一个登录注册界面

好的,这是一个比较常见的技术问题,我可以为您提供一些参考资料和思路。首先,您可以使用Spring Boot作为后端框架来处理用户认证和注册的逻辑,比如使用Spring Security实现用户登录认证。同时,您还需要设计相应的数据模型和数据库表结构来存储用户信息。在前端方面,您可以使用Vue.js作为框架来构建登录注册页面,使用Axios来发起API请求并和后端进行交互。当然,在实现过程中,还需要考虑一些具体细节,比如数据校验、安全性和用户体验等方面。希望这些信息能够帮助到您。
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。