1. 首页
  2. 文章中心
  3. complier

[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案

101 阅读 0 评论
我是靠谱客的博主 重要花瓣，最近开发中收集的这篇文章主要介绍[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录

内容：逻辑表达式的求值工具

具体要求

解决方案

设计文法

设计语法制导定义

编写词法分析器

编辑语法和语义分析：

实验难点

完整代码

实验结果

内容：逻辑表达式的求值工具

输入一个包含数值的逻辑表达式，输出计算其真值，和因短路操作而跳过的数值比较的次数。输出格式为Output: [true or false], [次数]。注意，逻辑表达式的计算符合短路算法。其中，!计入逻辑运算次数，而 == 或 != 只用于非布尔型的数值比较。例如： 

  • 输入：3 == 2
    输出：Output: false, 0 
  • 输入：3 > 2
    输出：Output: true, 0 
  • 输入：3 > 2 && 10 > 1
    输出：Output: true, 0 
  • 输入：3 > 2 && 10 > 12
    输出：Output: false, 0 
  • 输入：3 < 2 && 10 > 12
    输出：Output: false, 1 
  • 输入：3 < 2 && 10 < 12
    输出：Output: false, 1 
  • 输入：( 3 <= 2 || 13 <= 19 ) && 1 < 2 
    输出：Output: true, 0 
  • 输入：( 3 >= 2 || 13 <= 19 ) && 1 < 2 
    输出：Output: true, 1 
  • 输入：( 3 >= 2 || 13 <= 19 ) || 1 < 2 
    输出：Output: true, 2 
  • 输入：! ( 3 > 2 )
    输出：Output: false, 0 
  • 输入：! ( 3 > 2 || ( 13 < 19 || 1 < 2 ) )
    输出：Output: false, 2 

具体要求

(1) 为了解决上面问题，需要设计一个文法描述该问题的逻辑表达式，并设计语法制导定义求解最后的输出值。

(2) 根据(1)的文法，设计基于flex的词法分析器。具体形式为1个flex文件的源代码。

(3) 在(2)的基础上，设计基于bison的语法（同时包含语义）分析器。具体形式为1个bison文件的源代码。

(4) 在文档中，描述(1)的内容，以及(2)(3)的设计方案（不需要粘贴很多源代码到文档中）。文档中可以包括问题的难点、求解思路等，但不要包含显而易见的步骤。文档以清楚描述内容为主，不易过长，字数和篇幅不是采分点。

(5) 已知输入的表达式中不包含中文字符。文法应该能够兼容下面字符：数值比较<、<=、>、>=、==、!=，布尔比较&&、||、！，以及括号(、)。注意：== 或 != 只用于非布尔型的数值比较

(6) 词法分析和语法分析应具有基本的报错能力，例如对于不符合的语法，如输入了字母或者小数，输出”Error.”。

解决方案

  • 设计文法

(1)S -> R
(2)R -> R or R
(3)R -> R and R

(4)R -> ! R
(5)R -> ( R )
(6)R -> value < value

(7)R -> value <= value
(8)R -> value > value

(9)R -> value >= value

(10)R -> value == value

(11)R -> value !=value

  • 设计语法制导定义

该程序输出为逻辑表达式的值以及因短路机制而跳过的运算步骤，因此，为非终结符定义综合属性val、total和cut。value值为其对应的真假值，total为其包含的总运算次数，cut为其已跳过的运算次数。

产生式

语义规则

S -> R

If(R.val) print(“Output: true,”+ R.cut);

Else print(“Output:false,”+ R.cut)

R -> R1 or R2

R.val = R1.val || R2.val; R.total = R1.total + R2.total;

If(R1.val) R.cut = R1.cut + R2.total;

Else R.cut = R1.cut + R2.cut;

R -> R1 and R2

R.val = R1.val && R2.val; R.total = R1.total + R2.total;

If(R1.val) R.cut = R1.cut + R2.cut;

Else R.cut = R1.cut + R2.total;

R -> ! R1

R.val = !R1.val; R.total = R1.total + 1; R.cut = R1.cut;

R - > ( R )

R.val = R1.val; R.total = R1.total; R.cut = R1.cut;

R -> value < value

R.val = value < value; R.total = 1; R.cut = 0;

R -> value <= value

R.val = value <= value; R.total = 1; R.cut = 0;

R -> value > value

R.val = value > value; R.total = 1; R.cut = 0;

R -> value >= value

R.val = value >= value; R.total = 1; R.cut = 0;

R -> value == value

R.val = value == value; R.total = 1; R.cut = 0;

R -> value != value

R.val = value != value; R.total = 1; R.cut = 0;

  • 编写词法分析器

定义双符号非终结符：

NLT >=
NGT <=
EQL ==
NEQ !=
AND &&
OR ||
{NLT} {
yylval = *yytext;
return nlt;
}/* 此处以NLT为例 */

定义数字digit非终结符，需要做数值转换，将字符串转换为整型，用到atoi函数：

digit [0-9]
%%
{digit}+ {
yylval = atoi(yytext);
return VALUE; 
}

定义单符号终结符：

[()=!><n] {return *yytext;}

定义空白：

{whitespace}	{ ; }
{newline}	{ return 0; }
.	{
printf("Error! Wrong token '%s'.n", yytext);
exit(0);
}
  • 编译语法和语义分析器

设计非终结符结构，包含val、total和cut综合属性：

typedef struct
{
     int val;
     int total;
     int cut;
}myStruct;

定义token以及左右结合规则；其中除! 为右结合外，其余比较符号皆为左结合：

%token VALUE
%token nlt ngt eql neq and or 
%right   '!'
%left   '<'  '>' 
%left   nlt ngt eql neq and or

 

编辑语法和语义分析：

S: R {{if($1.val)printf("Output: true,%d",$1.cut);else printf("Output: false,%d",$1.cut); return 0;}}
;
R: 
  |R or R    {$$.val = $1.val || $3.val;
$$.total = $1.total + $3.total;
if($1.val) $$.cut = $1.cut + $3.total;
else $$.cut = $1.cut + $3.cut;}
  |R and R    {$$.val = $1.val && $3.val;
$$.total = $1.total + $3.total;
if($1.val) $$.cut = $1.cut + $3.cut;
else $$.cut = $1.cut + $3.total;}
  |'!' R         {$$.val =  ! $2.val; $$.total = $2.total + 1; $$.cut = $2.cut;}
  |'('R')'       {$$.val = $2.val; $$.total = $2.total; $$.cut = $2.cut;}
  |VALUE '<' VALUE   {$$.val = ($1.val < $3.val); $$.total = 1; $$.cut = 0;}
  |VALUE ngt VALUE   {$$.val = ($1.val <= $3.val); $$.total = 1; $$.cut = 0;}
  |VALUE '>' VALUE   {$$.val = ($1.val > $3.val); $$.total = 1; $$.cut = 0;}
  |VALUE nlt VALUE   {$$.val = ($1.val >= $3.val); $$.total = 1; $$.cut = 0;}
  |VALUE eql VALUE   {$$.val = ($1.val == $3.val); $$.total = 1; $$.cut = 0;}
  |VALUE neq VALUE   {$$.val = ($1.val != $3.val); $$.total = 1; $$.cut = 0;}

  • 实验难点

1、本实验在macOS系统上进行，与windows不同，在安装flex、bison和gcc后，可编写.l和.y文件，编译过程如下：

bison -d mytool.y
flex -omytool.yy.c mytool.l
gcc mytool.tab.c mytool.yy.c
./a.out

2、由于非终结符有多个综合属性，因此需要定义struct添加多个属性。

3、语义设计时需要注意优先级，依次为or and ! () < <= > >= == !=

4、在词法定义中，需要给双符号比较符定义别名，才可在之后设计词法；digit非终结符需要使用atoi方法将输入的字符串转换为int格式，否则在后续的比较中无法比较两位以上的数字。

  • 完整代码

mytool.l

%{
#include <stdio.h>
#include "mytool.tab.h"
%}
NLT >=
NGT <=
EQL ==
NEQ !=
AND &&
OR ||
whitespace [ tfv]
newline [rn]
digit	[0-9]
%%
{whitespace}	{ ; }
{newline}	{ return 0; }
{digit}+ {
yylval = atoi(yytext);
return VALUE;
}
[()=!><n]	{return *yytext;}
{NLT}	{
yylval = *yytext;
return nlt;
}
{NGT}	{
yylval = *yytext;
return ngt;
}
{EQL}	{
yylval = *yytext;
return eql;
}
{NEQ}	{
yylval = *yytext;
return neq;
}
{AND}	{
yylval = *yytext;
return and;
}
{OR}	{
yylval = *yytext;
return or;
}
.	{
printf("Error! Wrong token '%s'.n", yytext);
exit(0);
}
%%
int yywrap(void)
{
return 1;
}

mytool.y

%{
#include <stdio.h>
#ifndef BTOD_H_INCLUDED
#define BTOD_H_INCLUDED
typedef struct
{
int val;
int total;
int cut;
}myStruct;
#endif
#define YYSTYPE myStruct
int yylex(void);
void yyerror(char const *);
%}
%token VALUE
%token nlt ngt eql neq and or
%right
'!'
%left
'<'
'>'
%left
nlt ngt eql neq and or
%%
S: R {{if($1.val)printf("Output: true,%d",$1.cut);else printf("Output: false,%d",$1.cut); return 0;}}
;
R:
|R or R
{$$.val = $1.val || $3.val;
$$.total = $1.total + $3.total;
if($1.val) $$.cut = $1.cut + $3.total;
else $$.cut = $1.cut + $3.cut;}
|R and R
{$$.val = $1.val && $3.val;
$$.total = $1.total + $3.total;
if($1.val) $$.cut = $1.cut + $3.cut;
else $$.cut = $1.cut + $3.total;}
|'!' R
{$$.val =
! $2.val; $$.total = $2.total + 1; $$.cut = $2.cut;}
|'('R')'
{$$.val = $2.val; $$.total = $2.total; $$.cut = $2.cut;}
|VALUE '<' VALUE
{$$.val = ($1.val < $3.val); $$.total = 1; $$.cut = 0;}
|VALUE ngt VALUE
{$$.val = ($1.val <= $3.val); $$.total = 1; $$.cut = 0;}
|VALUE '>' VALUE
{$$.val = ($1.val > $3.val); $$.total = 1; $$.cut = 0;}
|VALUE nlt VALUE
{$$.val = ($1.val >= $3.val); $$.total = 1; $$.cut = 0;}
|VALUE eql VALUE
{$$.val = ($1.val == $3.val); $$.total = 1; $$.cut = 0;}
|VALUE neq VALUE
{$$.val = ($1.val != $3.val); $$.total = 1; $$.cut = 0;}
;
%%
int main()
{
yyparse();
return 0;
}
void yyerror(char const *msg)
{
fprintf(stderr, "%sn",msg);
}

  • 实验结果

        (太尴尬了，把experiment拼错了) 以下是要求给的数据：

(base) joseph@MacBook-Pro exepriment % ./a.out
3>5&&1<2
Output: false,1%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 == 2
Output: false,0%
(base) joseph@eMacBook-Pro exepriment % ./a.out
3 > 2
Output: true,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 > 2 && 10 > 1
Output: true,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 > 2 && 10 > 12
Output: false,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 > 2 && 10 > 12
Output: false,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 < 2 && 10 > 12
Output: false,1%
(base) joseph@MacBook-Pro exepriment % ./a.out
3 < 2 && 10 < 12
Output: false,1%
(base) joseph@MacBook-Pro exepriment % ./a.out
( 3 <= 2 || 13 <= 19 ) && 1 < 2
Output: true,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
( 3 >= 2 || 13 <= 19 ) && 1 < 2
Output: true,1%
(base) joseph@MacBook-Pro exepriment % ./a.out
( 3 >= 2 || 13 <= 19 ) || 1 < 2
Output: true,2%
(base) joseph@MacBook-Pro exepriment % ./a.out
! ( 3 > 2 )
Output: false,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
! ( 3 > 2 || ( 13 < 19 || 1 < 2 ) )
Output: false,2%

以下是扩展的数据和错误输入：

(base) joseph@MacBook-Pro exepriment % ./a.out
a > b
Error! Wrong token 'a'.
(base) joseph@MacBook-Pro exepriment % ./a.out
3.4 > 4.4
Error! Wrong token '.'.
(base) joseph@MacBook-Pro exepriment % ./a.out
3 > 4 , 2>3
Error! Wrong token ','.
(base) joseph@MacBook-Pro exepriment % ./a.out
1 == 1 == 1
Output: true,0%
(base) joseph@MacBook-Pro exepriment % ./a.out
! ( 3 > 2 || ! ( 13 < 19 || 1 < 2 ) )
Output: false,3%
(base) joseph@MacBook-Pro exepriment % ./a.out
! ( 3 > 2 && 4 < 5 ) && !( 3 > 1 || ! ( 4 < 1 && 2 < 1))
Output: true,3%
(base) joseph@MacBook-Pro exepriment % ./a.out
(! ( 3 > 2 && 4 < 5 ) )&& !( 3 > 1 || ! ( 4 < 1 && 2 < 1))
Output: false,5%

实验结果与预期相符。

最后

以上就是重要花瓣为你收集整理的[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案的全部内容，希望文章能够帮你解决[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(67)

相关文章

Lex和Yacc从入门到精通(1)－－环境配置篇
Lex和Yacc从入门到精通(1)－－环境配置篇
词法分析器的生成器——lex/flex1.词法分析器和语法分析器2.flex
词法分析器的生成器——lex/flex1.词法分析器和语法分析器2.flex
Lex和Yacc的入门lex和yacc简介lex使用yacc使用实例应用
Lex和Yacc的入门lex和yacc简介lex使用yacc使用实例应用
Lex+YACC or Flex+Bison
Lex+YACC or Flex+Bison
[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案
[编译原理]lex和bison实现逻辑表达式求值以及短路计算次数统计内容：逻辑表达式的求值工具解决方案
3.05 flex和bison进阶，产生C++语法分析器
3.05 flex和bison进阶，产生C++语法分析器
LEX&&YACC--编译界的神
LEX&&YACC--编译界的神
C语言变量的声明与定义
C语言变量的声明与定义

评论列表共有 0 条评论

立即
投稿
返回
顶部