我想为命题逻辑实现解析器，该解析器具有以下运算符，按优先级降序排列：
- 不是p
- p 和 q
- p 或 q
- 如果 P 则 q
- p IFF q
- 如果 p 则 q ELSE r
主要问题在于 IF-THEN-ELSE 运算符。没有它，我能够正确地编写语法。目前我的 yacc 文件看起来像
%term
PARSEPROG | AND | NOT | OR | IF | THEN | ELSE | IFF | LPAREN | RPAREN | ATOM of string | SEMICOLON | EOF
%nonterm
start of Absyn.program | EXP of Absyn.declaration
%start start
%eop EOF SEMICOLON
%pos int
%verbose
%right ELSE
%right IFF
%right THEN
%left AND OR
%left NOT
%name Fol
%noshift EOF
%%
start : PARSEPROG EXP (Absyn.PROGRAM(EXP))
EXP: ATOM ( Absyn.LITERAL(ATOM) )
| LPAREN EXP RPAREN (EXP)
| EXP AND EXP ( Absyn.CONJ(EXP1, EXP2) )
| EXP OR EXP ( Absyn.DISJ(EXP1, EXP2) )
| IF EXP THEN EXP ELSE EXP ( Absyn.IFTHENELSE(EXP1, EXP2, EXP3) )
| IF EXP THEN EXP ( Absyn.IMPLI(EXP1, EXP2) )
| EXP IFF EXP ( Absyn.BIIMPLI(EXP1, EXP2) )
| NOT EXP ( Absyn.NEGATION(EXP) )
但我似乎没有得到如何消除减少班次冲突的正确想法。正确解析的一些示例包括：
- 如果 A 则 如果 B 则 c________a->(B->C) 如果 a 则
- 如果 b 则 c 否则 d IFF e 或 f_______IFTHENELSE(a，b->c，d<=>e/\f)
任何帮助/指示都会非常有帮助。谢谢。
让我的Yacc坐起来乞求
我比以往任何时候都更加确信，如果可能的话，这里的正确方法是 GLR 语法。然而，受@Kaz的启发，我用 LALR(1) 语法(甚至不使用优先级声明)制作了以下 yacc/bison 语法。
当然，它作弊了，因为这个问题不能用 LALR(1) 语法来解决。在适当的时间间隔内，它遍历构造的IF THEN和IF THEN ELSE表达式树，并根据需要移动ELSE子句。
需要重新检查可能运动的节点被赋予 AST 节点类型IFSEQ，并且ELSE子句使用经典的匹配 if/unmatched-if 语法附加传统的最紧密匹配语法。完全匹配的IF THEN ELSE子句不需要重新排列;树重写将应用于与右操作数不匹配的第一个ELSE关联的表达式(如果有的话)。将IF表达式的完全匹配前缀与需要重新排列的尾部分开，几乎需要复制一些规则;几乎重复的规则的不同之处在于，如果IFSEQ节点，则直接生成TERNARY节点。
为了正确回答这个问题，还需要重新排列一些IFF节点，因为IFF比THEN条款绑定得更弱，比ELSE条款更紧密。我认为这意味着：
IF p THEN q IFF IF r THEN s ==> ((p → q) ↔ (r → s))
IF p THEN q IFF r ELSE s IFF t ==> (p ? (q ↔ r) : (s ↔ t))
IF p THEN q IFF IF r THEN s ELSE t IFF u ==> (p ? (q ↔ (r → s)) : (t ↔ u))
虽然我不确定这是所要求的(尤其是最后一个)，我真的不认为这是一个好主意。在下面的语法中，如果您希望IFF应用于IF p THEN q子表达式，则必须使用括号;IF p THEN q IFF r会产生p → (q ↔ r)，p IFF IF q THEN r是语法错误。
坦率地说，我认为使用箭头表示条件和双条件(如上面的光泽)以及仅将IF THEN ELSE用于三元选择器表达式(上面用 C 风格的? :语法编写，这是另一种可能性)会更容易。这将产生更少的惊喜。但这不是我的语言。
具有浮动优先级的双条件运算符的一种解决方案是分两次解析。第一次传递将仅识别没有附加ELSE的IF p THEN q运算符，使用类似于此处提出的机制，并通过删除IF和更改THEN的拼写将它们更改为p -> q。其他运算符不会被解析，括号将被保留。然后，它将生成的令牌流馈送到具有更传统语法样式的第二个 LALR 解析器中。我可能会开始编码，只是因为我认为两遍野牛解析器偶尔有用，而且很少有例子。
这是树重写解析器。对于长度，我深表歉意：
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void yyerror(const char* msg);
int yylex(void);
typedef struct Node Node;
enum AstType { ATOM, NEG, CONJ, DISJ, IMPL, BICOND, TERNARY,
IFSEQ
};
struct Node {
enum AstType type;
union {
const char* atom;
Node* child[3];
};
};
Node* node(enum AstType type, Node* op1, Node* op2, Node* op3);
Node* atom(const char* name);
void node_free(Node*);
void node_print(Node*, FILE*);
typedef struct ElseStack ElseStack;
struct ElseStack {
Node* action;
ElseStack* next;
};
ElseStack* build_else_stack(Node*, ElseStack*);
ElseStack* shift_elses(Node*, ElseStack*);
%}
%union {
const char* name;
struct Node* node;
}
%token <name> T_ID
%token T_AND "and"
T_ELSE "else"
T_IF "if"
T_IFF "iff"
T_NOT "not"
T_OR "or"
T_THEN "then"
%type <node> term conj disj bicond cond mat unmat tail expr
%%
prog : %empty | prog stmt;
stmt : expr 'n' { node_print($1, stdout); putchar('n'); node_free($1); }
| 'n'
| error 'n'
term : T_ID { $$ = atom($1); }
| "not" term { $$ = node(NEG, $2, NULL, NULL); }
| '(' expr ')' { $$ = $2; }
conj : term
| conj "and" term { $$ = node(CONJ, $1, $3, NULL); }
disj : conj
| disj "or" conj { $$ = node(DISJ, $1, $3, NULL); }
bicond: disj
| disj "iff" bicond { $$ = node(BICOND, $1, $3, NULL); }
mat : bicond
| "if" expr "then" mat "else" mat
{ $$ = node(IFSEQ, $2, $4, $6); }
unmat: "if" expr "then" mat
{ $$ = node(IFSEQ, $2, $4, NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, $2, $4, NULL); }
| "if" expr "then" mat "else" unmat
{ $$ = node(IFSEQ, $2, $4, $6); }
tail : "if" expr "then" mat
{ $$ = node(IFSEQ, $2, $4, NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, $2, $4, NULL); }
cond : bicond
| tail { shift_elses($$, build_else_stack($$, NULL)); }
| "if" expr "then" mat "else" cond
{ $$ = node(TERNARY, $2, $4, $6); }
expr : cond
%%
/* Walk the IFSEQ nodes in the tree, pushing any
* else clause found onto the else stack, which it
* returns.
*/
ElseStack* build_else_stack(Node* ifs, ElseStack* stack) {
if (ifs && ifs->type != IFSEQ) {
stack = build_else_stack(ifs->child[1], stack);
if (ifs->child[2]) {
ElseStack* top = malloc(sizeof *top);
*top = (ElseStack) { ifs->child[2], stack };
stack = build_else_stack(ifs->child[2], top);
}
}
return stack;
}
/* Walk the IFSEQ nodes in the tree, attaching elses from
* the else stack.
* Pops the else stack as it goes, freeing popped
* objects, and returns the new top of the stack.
*/
ElseStack* shift_elses(Node* n, ElseStack* stack) {
if (n && n->type == IFSEQ) {
if (stack) {
ElseStack* top = stack;
stack = shift_elses(n->child[2],
shift_elses(n->child[1], stack->next));
n->type = TERNARY;
n->child[2] = top;
free(top);
}
else {
shift_elses(n->child[2],
shift_elses(n->child[1], NULL));
n->type = IMPL;
n->child[2] = NULL;
}
}
return stack;
}
Node* node(enum AstType type, Node* op1, Node* op2, Node* op3) {
Node* rv = malloc(sizeof *rv);
*rv = (Node){type, .child = {op1, op2, op3}};
return rv;
}
Node* atom(const char* name) {
Node* rv = malloc(sizeof *rv);
*rv = (Node){ATOM, .atom = name};
return rv;
}
void node_free(Node* n) {
if (n) {
if (n->type == ATOM) free((char*)n->atom);
else for (int i = 0; i < 3; ++i) node_free(n->child[i]);
free(n);
}
}
const char* typename(enum AstType type) {
switch (type) {
case ATOM: return "ATOM";
case NEG: return "NOT" ;
case CONJ: return "CONJ";
case DISJ: return "DISJ";
case IMPL: return "IMPL";
case BICOND: return "BICOND";
case TERNARY: return "TERNARY" ;
case IFSEQ: return "IF_SEQ";
}
return "**BAD NODE TYPE**";
}
void node_print(Node* n, FILE* out) {
if (n) {
if (n->type == ATOM)
fputs(n->atom, out);
else {
fprintf(out, "(%s", typename(n->type));
for (int i = 0; i < 3 && n->child[i]; ++i) {
fputc(' ', out); node_print(n->child[i], out);
}
fputc(')', out);
}
}
}
void yyerror(const char* msg) {
fprintf(stderr, "%sn", msg);
}
int main(int argc, char** argv) {
return yyparse();
}
词法分析器几乎是微不足道的。(这个使用小写关键字，因为我的手指更喜欢这样，但改变起来微不足道。
%{
#include "ifelse.tab.h"
%}
%option noinput nounput noyywrap nodefault
%%
and { return T_AND; }
else { return T_ELSE; }
if { return T_IF; }
iff { return T_IFF; }
not { return T_NOT; }
or { return T_OR; }
then { return T_THEN; }
[[:alpha:]]+ { yylval.name = strdup(yytext);
return T_ID; }
([[:space:]]{-}[n])+ ;
n { return 'n'; }
. { return *yytext;}
如前所述，解析器/词法分析器一次读取一行，并打印每行的 AST(因此不允许使用多行表达式)。我希望很清楚如何改变它。
处理此要求的一种相对简单的方法是创建一个过度生成的语法，然后拒绝我们不希望使用语义的语法。
具体来说，我们使用这样的语法：
expr : expr AND expr
| expr OR expr
| expr IFF expr
| IF expr THEN expr
| expr ELSE expr /* generates some sentences we don't want! */
| '(' expr ')'
| ATOM
;
请注意，ELSE只是一个普通的低优先级运算符：任何表达式都可以后跟ELSE和另一个表达式。但是在语义规则中，我们实现了ELSE左侧是否为IF表达式的检查。如果没有，那么我们会引发错误。
这种方法不仅易于实现，而且易于为最终用户记录，因此易于理解和使用。最终用户可以接受一个简单的理论，即ELSE只是另一个优先级非常低的二进制运算符，以及当它不与IF/THEN结合使用时拒绝它的规则。
这是我编写的完整程序的测试运行(使用经典的Yacc，在C中)：
$ echo 'a AND b OR c' | ./ifelse
OR(AND(a, b), c)
$ echo 'a OR b AND c' | ./ifelse
OR(a, AND(b, c))
$ echo 'IF a THEN b' | ./ifelse
IF(a, b)
普通的单IF/ELSE做我们想做的事：
$ echo 'IF a THEN b ELSE c' | ./ifelse
IFELSE(a, b, c)
您追求的关键是：
$ echo 'IF a THEN IF x THEN y ELSE c' | ./ifelse
IFELSE(a, IF(x, y), c)
正确地，ELSE与外部IF一起使用.这是错误ELSE的错误情况：
$ echo 'a OR b ELSE c' | ./ifelse
error: ELSE must pair with IF
<invalid>
以下是括号，用于强制通常的"else with most if"行为：
$ echo 'IF a THEN (IF x THEN y ELSE c)' | ./ifelse
IF(a, IFELSE(x, y, c))
该程序通过构建 AST 然后遍历它以前缀F(X, Y)语法打印它来显示它正在使用的解析。(为此，作为一名 Lisp 程序员，我不得不稍微抑制一下呕吐反射)。
AST 结构还允许ELSE规则检测其左参数是否为正确类型的表达式。
注意：您可能希望处理以下内容，但事实并非如此：
$ echo 'IF a THEN IF x THEN y ELSE z ELSE w' | ./ifelse
error: ELSE must pair with IF
<invalid>
这里的问题是ELSE w与IFELSE表达式配对。
一种更复杂的方法可能是可能的，可能会很有趣。解析器可以将ELSE视为普通的二进制运算符，并以这种方式生成AST。然后，整个单独的遍历可以检查树的有效ELSE使用情况，并根据需要对其进行转换。或者，也许我们可以在这里发挥ELSE的关联性，并以某种合适的方式处理解析器操作中的级联ELSE。
完整的源代码，我保存在一个名为ifelse.y的文件中，并使用以下方法构建：
$ yacc ifelse.y
$ gcc -o ifelse y.tab.c
在这里：
%{
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
typedef struct astnode {
int op;
struct astnode *left, *right;
char *lexeme;
} astnode;
void yyerror(const char *s)
{
fprintf(stderr, "error: %sn", s);
}
void *xmalloc(size_t size)
{
void *p = malloc(size);
if (p)
return p;
yyerror("out of memory");
abort();
}
char *xstrdup(char *in)
{
size_t sz = strlen(in) + 1;
char *out = xmalloc(sz);
return strcpy(out, in);
}
astnode *astnode_cons(int op, astnode *left, astnode *right, char *lexeme)
{
astnode *a = xmalloc(sizeof *a);
a->op = op;
a->left = left;
a->right = right;
a->lexeme = lexeme;
return a;
}
int yylex(void);
astnode *ast;
%}
%union {
astnode *node;
char *lexeme;
int none;
}
%token<none> '(' ')'
%token<lexeme> ATOM
%left<none> ELSE
%left<none> IF THEN
%right<none> IFF
%left<none> OR
%left<none> AND
%type<node> top expr
%%
top : expr { ast = $1; }
expr : expr AND expr
{ $$ = astnode_cons(AND, $1, $3, 0); }
| expr OR expr
{ $$ = astnode_cons(OR, $1, $3, 0); }
| expr IFF expr
{ $$ = astnode_cons(IFF, $1, $3, 0); }
| IF expr THEN expr
{ $$ = astnode_cons(IF, $2, $4, 0); }
| expr ELSE expr
{ if ($1->op != IF)
{ yyerror("ELSE must pair with IF");
$$ = 0; }
else
{ $$ = astnode_cons(ELSE, $1, $3, 0); } }
| '(' expr ')'
{ $$ = $2; }
| ATOM
{ $$ = astnode_cons(ATOM, 0, 0, $1); }
;
%%
int yylex(void)
{
int ch;
char tok[64], *te = tok + sizeof(tok), *tp = tok;
while ((ch = getchar()) != EOF) {
if (isalnum((unsigned char) ch)) {
if (tp >= te - 1)
yyerror("token overflow");
*tp++ = ch;
} else if (isspace(ch)) {
if (tp > tok)
break;
} else if (ch == '(' || ch == ')') {
if (tp == tok)
return ch;
ungetc(ch, stdin);
break;
} else {
yyerror("invalid character");
}
}
if (tp > tok) {
yylval.none = 0;
*tp++ = 0;
if (strcmp(tok, "AND") == 0)
return AND;
if (strcmp(tok, "OR") == 0)
return OR;
if (strcmp(tok, "IFF") == 0)
return IFF;
if (strcmp(tok, "IF") == 0)
return IF;
if (strcmp(tok, "THEN") == 0)
return THEN;
if (strcmp(tok, "ELSE") == 0)
return ELSE;
yylval.lexeme = xstrdup(tok);
return ATOM;
}
return 0;
}
void ast_print(astnode *a)
{
if (a == 0) {
fputs("<invalid>", stdout);
return;
}
switch (a->op) {
case ATOM:
fputs(a->lexeme, stdout);
break;
case AND:
case OR:
case IF:
case IFF:
switch (a->op) {
case AND:
fputs("AND(", stdout);
break;
case OR:
fputs("OR(", stdout);
break;
case IF:
fputs("IF(", stdout);
break;
case IFF:
fputs("IFF(", stdout);
break;
}
ast_print(a->left);
fputs(", ", stdout);
ast_print(a->right);
putc(')', stdout);
break;
case ELSE:
fputs("IFELSE(", stdout);
ast_print(a->left->left);
fputs(", ", stdout);
ast_print(a->left->right);
fputs(", ", stdout);
ast_print(a->right);
putc(')', stdout);
break;
}
}
int main(void)
{
yyparse();
ast_print(ast);
puts("");
return 0;
}