如果没有解析器生成器,如何用 C 或 Objective-C 编写解析器?
我正在尝试用 C 或 Objective-C 制作一个计算器,它接受 2920 的字符串
8/2+4(3*9)^2
并返回答案 2920。我不想使用像 Lex 或 Yacc 这样的生成器,所以我想从头开始编码。我该怎么做呢?除了《龙》这本书之外,还有其他涉及此主题的推荐文本吗?
I am trying to make a calculator in C or Objective-C that accepts a string along the lines of
8/2+4(3*9)^2
and returns the answer 2920. I would prefer not to use a generator like Lex or Yacc, so I want to code it from the ground up. How should I go about doing this? Other than the Dragon book, are there any recommended texts that cover this subject matter?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(7)
如果我没记错的话,你可以用两个堆栈来解决这个问题,一个用于运算符,另一个用于操作数。
// OPTR stack: store operators
// OPND stack: store operands
// OP: predefined set of operators
OperandType EvaluateExpression(){
InitStack(OPET);Push(OPTR,'#');
initStack(OPND);c=getchar();
while(c!='#'||GetTop(OPTR)!='#'){
if(!In(c,OP)){Push((OPND,c);c=getchar();} //Push to stack if not operator
else
switch(Precede(GetTop(OPTR),c){
//Top element in stack has a lower priority
case '<':
Push(OPTR,c); c=getch();
break;
case '=':
Pop(OPTR,x); c=getch();
break;
//Pop top element and push back the calculated result
case '>':
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND);
}
调车场算法已经提到过。另一种经典的方法是简单的递归下降。这是我多年前写的一篇相当短的文章:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void expression(void);
void show(int ch) {
putchar(ch);
putchar(' ');
}
int token() {
int ch;
while (isspace(ch=getchar()))
;
return ch;
}
void factor() {
int ch = token();
if (ch == '(') {
expression();
ch = token();
if (ch != ')') {
fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch);
exit(EXIT_FAILURE);
}
}
else
show(ch);
}
void term() {
int ch;
factor();
ch = token();
if (ch == '*' || ch == '/') {
term();
show(ch);
}
else
ungetc(ch, stdin);
}
void expression() {
int ch;
term();
ch = token();
if (ch == '-' || ch=='+') {
expression();
show(ch);
}
else
ungetc(ch, stdin);
}
int main(int argc, char **argv) {
expression();
return 0;
}
请注意,这个特定的文章只是解析输入,并将其转换为 RPN 形式。如果您想解释结果,则可以用实际评估表达式该部分的结果来代替打印每个操作数/运算符。
我在大学计算机科学专业三年级时在《CSE340:编程语言简介》中做到了这一点。因此,如果您真的想要从头开始编写解析器,请做好准备,这可能是“一个学期的项目”。
您需要标记、解析、构建抽象表达式树、评估等。
我们使用 劳登的编程语言:原理与实践。我喜欢它。尽管它并没有很好地引导您完成实施过程。
当然,这不仅仅是“从头开始编码”。您需要制定语法,然后构建一个解析器来处理规则......除了学习活动之外,我不确定您为什么要这样做。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
Dave DeLong 的 DDMathParser 类可能会为您节省大量时间和麻烦。
Dave DeLong's DDMathParser class may save you a lot of time and trouble.