一个简单的手动编写的脚本解析器

arussell

4.41/5 (10投票s)

2004年12月1日

9分钟阅读

115340

2706

一个简单的脚本解析器和引擎，用于演示如何编写解析器以及递归下降语句求值。

下载源文件 - 33.2 Kb

引言

这是我写的第三个解析器，比前两个好用了一些。这个解析器的目标是易于扩展、易于其他程序员理解、易于嵌入到其他项目中。我还希望它足够简单，让中级程序员能够理解代码的工作原理。我已经部分成功了。

虽然添加更多运算符或内置函数仍然不太容易，但代码比我以前的尝试透明得多。当已经有非常好的解析器和用于根据语言描述生成解析器C代码的工具时，我为什么还要这样做呢？这些工具对于刚开始编写解析器的人来说往往有点过于复杂。这段代码足够小，可以看到一个简单解析器的工作原理，但又具有足够的功能，需要比非常简单的解析器更好的设计。它适合学生学习如何组装解析器。

特点

用户定义函数
支持用户定义函数的递归和嵌套调用
全局变量和局部变量
丰富的运算符集
必须声明所有变量
生成简单的字节码。
体积小巧，易于插入现有项目。

不足之处

没有头文件 – 无法调用脚本中稍后定义的函数。函数可以调用自身。
无法在复杂语句中调用函数。函数值可以赋值给变量，但必须是语句的唯一项，例如：y=foo{}; 是正确的，y=x + foo{}; 是错误的。
使用简单的递归下降方法来求值语句。这使得理解解析器的这一部分工作原理变得容易，但它会生成低效的字节码。让解析器生成逆波兰语句会使引擎更高效和灵活。
数组仅限于一维。
函数参数最多20个。
函数不能有数组参数

关于解析器和引擎的注意事项

这是一个单趟解析器。它将整个脚本文本读入内存，并一次性从头到尾进行解析。在主解析器传递之前，会有一个额外的传递来处理指令。除了注释之外，空白字符都会被忽略。

解析器一次读取一个“令牌”。令牌是一个有效的文本片段，例如“int”、“+”、“==”、变量名或文字值。解析器硬编码检查语法。例如，如果它遇到一个表示整数的文字字符串，它会期望后面跟着一个赋值。这种逻辑是硬编码的，而不是由语言描述驱动的。

解析变量

当声明变量时，它们的类型、名称和位置都会被保存。当变量稍后在语句中遇到时，解析器会生成使用变量类型和位置来获取或设置其值的代码。

全局变量从字节流的开头开始，随着更多全局变量的声明而简单地添加。在字节码中，全局变量将是一个指示类型的字节（int、float等…），后跟一个整数，该整数是变量相对于字节码开头的偏移量。

局部变量则大不相同。代码支持递归，因此局部变量的位置必须根据函数调用嵌套的层数而改变。当调用函数时，指向当前局部变量栈的指针会进行调整。局部变量始终相对于此指针的当前位置定位，而不是像全局变量那样相对于固定位置。当解析函数调用时，当前局部变量指针会增加函数局部变量的大小，并在退出时，将相同的量从局部变量指针中移除。然后，局部变量将相对于此移动指针进行检索。

如果 / 当

这是一个单趟解析器。当解析 if 时，它会被替换为求值逻辑语句的代码，如果逻辑语句为假，则跳过 if 块的末尾。解析器尚不知道要跳到哪里，所以我们把 goto 的地址留空，并将此空地址保存在一个仅在解析时存在的临时栈中。然后，当我们到达 end 语句时，我们可以填写缺失的 goto 地址，并从临时栈中移除 goto。

while、break 和 else 语句以类似的方式处理。使用地址栈允许解析器支持嵌套的流程控制。

启动代码

解析器硬编码首先运行用户函数“main”。字节流的开头放置了一些字节代码，用于初始化数据指针并调用 main 函数。

我本可以做得不同的地方

尽管这是我过去十年中编写的第三个解析器，但我做出了一些糟糕的设计决策，导致我不得不重写解析器的很大一部分。我第一次处理变量的尝试对全局变量运行良好，但根本没有处理局部变量。重写。我用于求值语句的方法在没有函数调用时运行良好。当我添加函数调用时，我不得不再次重写，并且解析器仍然仅限于在语句中单独进行函数调用。

如果我有时间重做这个，我将创建一个更严谨的设计文档——特别是对于解析器发出的字节码。我一开始只列出了功能清单和脑海中模糊的设计。这不是理想的编程实践！如果我重新开始，我将设计出一种更好、更通用的方法来解析和求值复杂语句。我使用的方法，虽然最初在不担心函数调用的情况下很容易实现，但有许多限制和权宜之计来处理函数调用。我还会仔细研究现有编译器如何处理变量和函数调用。C 语言和其他简单语言如何处理这些任务中蕴含着很多智慧。

求值语句

解析器对语句的重新排序不多。它确实改变了赋值的完成方式，但赋值右侧的语句基本上只是被相同形式的字节码替换。在运行时，语句使用简单的递归下降方法求值。这是一种易于手动编码的方法，但生成的字节码效率不高。一个更有野心的解析器可能会生成逆波兰语句，或者以其他方式重新排序语句，以便可以使用更简单的语句求值器更快地运行。

让我们看一个简单的语句

4 + 3 * 5

为了正确求值，必须首先执行 3*5。递归下降通过扫描语句中优先级更高的运算符，求值它们，然后用结果替换求值项来完成此操作。这种扫描和替换会重复进行，直到只剩下一个值。

1^st pass 
4+15
2^nd pass
19 – all done

A second example
4 + (3*2+4) – 2
1^st pass
4+(6+4)-2
2^nd
4+(10)-2
3^rd
4+10-2
4^th
14-2
5^th
12 – all done

字节码引擎实际上会将一次传递的结果复制到原始语句的顶部（必要时用空运算符填充），直到只剩下一个文字值。语句的副本在解析时实际上会被销毁，因此会对其进行求值。这种破坏性求值是重新排序语句更好的另一个原因。由于脚本支持循环，因此需要一个副本。

在其他解析器中，我将语句转换为语句的链表，这使得代码更易于阅读，但也更慢。然后对链表进行求值，并根据需要替换和删除求值过的节点。

在函数 evaluate_int_exp() 中，您会看到它通过扫描优先级更高的语句，然后递归地在语句的子部分上调用 evaluate_in_exp() 来实现，直到整个语句简化为一个文字值。

数据类型

整数，1, 2, 3
字符 'a', 'b', 'c'
浮点数，1.2, 1.0, 9.9
数组
整数
字符 "abcded", "\n", "\t"
Float
仅限一维
指针？ – 否，但可以将字符串赋给字符数组

像 C 语言一样声明。

int
float
char
int [ ]
float [ ]
char [ ]

运算符

运算符	优先级	整数函数	浮点函数	字符串函数
`[ ]`	0	数组元素	数组元素	数组元素
`=`	0	赋值	赋值	赋值
`( )`	1	改变优先级	改变优先级	不适用
`!`	2	逻辑非	逻辑非	不适用
`-`	2	取反	取反	不适用
`~`	2	按位非	不适用	不适用
`*`	3	多个	多个	不适用
`/`	3	Divide	Divide	不适用
`%`	3	模除	模除	不适用
`+`	4	Add	Add	连接
`-`	4	Subtract	Subtract	不适用
`^`	5	按位异或	不适用	不适用
`&`	5	按位与	不适用	不适用
`\|`	5	按位或	不适用	不适用
`==`	6	测试相等性	测试相等性	测试相等性
`<=`	6	测试小于等于	测试小于等于	小于等于
`<`	6	小于	小于	小于
`>=`	6	大于等于	大于等于	大于等于
`>`	6	大于	大于	大于
`&&`	6	逻辑与	逻辑与	不适用
`\|\|`	6	逻辑或	逻辑或	不适用
`//`	不适用	注释	注释	注释
`atoi`	2	不适用	不适用	转换为 `int`
`atof`	2	不适用	不适用	转换为 `float`
`itoa`	2	转换为 `str`	不适用	不适用
`ftoa`	2	不适用	转换为 `str`	不适用

流程控制

while
if
if else
break
continue
end

内置函数

print

print 后跟逗号分隔的语句列表。例如：

print "hi world ", x, " that was x\n";

用户函数定义

func type name {parms};
end

返回类型必须是 int 或 float。数组不能作为参数。最多 20 个参数。例如：

func int fubar {int x, int y, float b};
  body;
end;

调用一个函数

fubar {1, 2, 3, aa};

或

x=fubar {1, 2, 3, aa};

不能在复杂语句中放置函数

X=fubar(1,2,3, aa} + 99;  // NOT allowed

范围

全局变量——所有在函数外部声明的变量。
局部变量——在函数内部声明的变量。
参数被视为局部变量。

指令

指令必须放在注释中。它们用于设置变量和调用堆栈的保留大小。

// $globalsize = 静态全局变量的字节大小（不是堆栈）
// $localsize = 局部变量堆栈的字节大小
// $parmsize = 参数堆栈的字节大小
// $stacksize = 代码堆栈的字节大小

默认每个为 64Kb。

语句

语句可以包含文字、变量和运算符。语句总是以分号“;”结尾。

包含函数的语句不能包含其他项，即，多项或单个函数调用。例如：

i=1+j*5;

或者

i=f1{};

数组索引可以是语句。

示例脚本

// test file

int x;
int i,j,k;
int ii[100],ij, ik;
float f, g;
float ff[10];
char s [ 100 ] , b, #9; #9; c;
char s2[100];
// ---------------------------------------------------------
func int test{};
  int y;
  print "at top of test\n";
  s[0]='a';
  s[1]=0;
  print "s = ", s, " s[0] = ", s[0], "\n";
  s="I am the cat " + "Hi World\n";
  s2=s;
  print "s = ", s, " s2 = ", s2, " newline\n";
  print "Hi world\n";
  print "Hi world tab\t cr\r world\n";
  x=43;
  y=5;
  ii[34]=x + y;
  ii[x+y]=5;
  print "ii[34] = ", ii[34], "\n";
  print ">x +10 = < ", x + 10, " y="y, "ii[2]=", ii[2], " ii[34] =", ii[34], "\n";
  print "(4-2)*5 = ", (4-2) *5, "\n";
  b='a';
  print "b = ", b, "\n";
  x=5;
  y=10;
  print "x=", x, " y=",y,"\n";
  if 1;
    print "before if break\n";
    break;
    print "after if break\n";
  end
  while x > 0;
    x=x-1;
    print "x=", x, "\n";
    // continue;
    if x > 2;
      print " x > 2\n";
    else
      print " x is not > 2\n";
    end
    print "before the break\n";
    break;
    print "past the break\n";
  end
  print "at the end, past the while\n";
end

// ----------------------------------------------------
func int foo1{};
  set 5;
end
// ----------------------------------------------------
func int foo2{int x, int y};
  set x*y;
end
// ----------------------------------------------------
func int main{};
  // locals
  int y, z;
  float m;
  print "top of main\n";
  print "call test next\n";
  test{};
  m=(1.0 + 0.5) * 20.0;
  print "m=",m,"\n";
  x=foo1{};
  y=10;
  z= (10 + y)*x;
  print "z = ", z, "\n";
  print "x=", x, " y=",y,"\n";
  while x > 0;
    x=x-1;
    if x > 2;
      print " x > 2\n";
    else
      print " x is not > 2\n";
    end
    print "x=", x, "\n";
  end
  print "at the end, past the if/while\n";
  x=5;
  y=6;
  x=foo2{x,y};
  print "x of foo2=", x, "\n";
end