使用 IF-THEN-ELSE 三元运算符的命题逻辑解析器冲突
Conflicts in Parser for Propositional logic with IF-THEN-ELSE ternary operator
我想为命题逻辑实现解析器，它具有以下优先级递减的运算符：
- 不是p
- p 和 q
- p 或 q
- 如果 p 那么 q
- p 敌我识别 q
- 如果 p 那么 q 否则 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)
- IF a THEN IF b THEN c ELSE d IFF e OR f_______IFTHENELSE(a,b->c,d<=>e/\f)
任何 help/pointers 都会很有帮助。谢谢
处理此要求的一种相对简单的方法是创建过度生成的语法，然后使用语义拒绝我们不想要的语法。
具体来说，我们使用这样的语法：
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 closest 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: %s\n", 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 = ; }
expr : expr AND expr
{ $$ = astnode_cons(AND, , , 0); }
| expr OR expr
{ $$ = astnode_cons(OR, , , 0); }
| expr IFF expr
{ $$ = astnode_cons(IFF, , , 0); }
| IF expr THEN expr
{ $$ = astnode_cons(IF, , , 0); }
| expr ELSE expr
{ if (->op != IF)
{ yyerror("ELSE must pair with IF");
$$ = 0; }
else
{ $$ = astnode_cons(ELSE, , , 0); } }
| '(' expr ')'
{ $$ = ; }
| ATOM
{ $$ = astnode_cons(ATOM, 0, 0, ); }
;
%%
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;
}
让我的 Yacc 坐起来乞求
我比以往任何时候都更加确信这里正确的方法是 GLR 语法，如果可能的话。然而，受@Kaz 的启发，我使用 LALR(1) 语法生成了以下 yacc/bison 语法（甚至没有使用优先级声明）。
当然，它作弊了，因为这个问题不能用 LALR(1) 文法来解决。在适当的时间间隔，它遍历 IF THEN 和 IF THEN ELSE 表达式的构造树，并根据需要移动 ELSE 子句。
需要重新检查可能运动的节点被赋予 AST 节点类型 IFSEQ 并且 ELSE 子句附加了传统的最紧密匹配语法，使用经典 matched-if/unmatched-if 语法。完全匹配的 IF THEN ELSE 子句不需要重新排列；树重写将应用于与右手操作数不匹配的第一个 ELSE 关联的表达式（如果有的话）。将 IF 表达式的完全匹配前缀与需要重新排列的尾部分开需要几乎重复一些规则；几乎重复的规则的不同之处在于它们的操作直接产生 TERNARY 个节点，而不是 IFSEQ 个节点。
为了正确回答问题，还需要重新排列一些 IFF 节点，因为 IFF 比 THEN 子句更弱，比 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 和将它们更改为 p -> q 和更改 THEN 的拼写。其他运算符将不会被解析，括号将被保留。然后它将生成的令牌流馈送到具有更传统语法样式的第二个 LALR 解析器。我可能会开始编写代码，只是因为我认为两次传递的 bison 解析器偶尔有用，而且周围几乎没有示例。
这是树重写解析器。对于长度，我深表歉意：
%{
#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(, stdout); putchar('\n'); node_free(); }
| '\n'
| error '\n'
term : T_ID { $$ = atom(); }
| "not" term { $$ = node(NEG, , NULL, NULL); }
| '(' expr ')' { $$ = ; }
conj : term
| conj "and" term { $$ = node(CONJ, , , NULL); }
disj : conj
| disj "or" conj { $$ = node(DISJ, , , NULL); }
bicond: disj
| disj "iff" bicond { $$ = node(BICOND, , , NULL); }
mat : bicond
| "if" expr "then" mat "else" mat
{ $$ = node(IFSEQ, , , ); }
unmat: "if" expr "then" mat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" mat "else" unmat
{ $$ = node(IFSEQ, , , ); }
tail : "if" expr "then" mat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, , , NULL); }
cond : bicond
| tail { shift_elses($$, build_else_stack($$, NULL)); }
| "if" expr "then" mat "else" cond
{ $$ = node(TERNARY, , , ); }
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, "%s\n", 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;}
如所写，parser/lexer 一次读取一行，并为每一行打印 AST（因此不允许使用多行表达式）。我希望清楚如何更改它。
我想为命题逻辑实现解析器，它具有以下优先级递减的运算符：
- 不是p
- p 和 q
- p 或 q
- 如果 p 那么 q
- p 敌我识别 q
- 如果 p 那么 q 否则 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)
- IF a THEN IF b THEN c ELSE d IFF e OR f_______IFTHENELSE(a,b->c,d<=>e/\f)
任何 help/pointers 都会很有帮助。谢谢
处理此要求的一种相对简单的方法是创建过度生成的语法，然后使用语义拒绝我们不想要的语法。
具体来说，我们使用这样的语法：
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 closest 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: %s\n", 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 = ; }
expr : expr AND expr
{ $$ = astnode_cons(AND, , , 0); }
| expr OR expr
{ $$ = astnode_cons(OR, , , 0); }
| expr IFF expr
{ $$ = astnode_cons(IFF, , , 0); }
| IF expr THEN expr
{ $$ = astnode_cons(IF, , , 0); }
| expr ELSE expr
{ if (->op != IF)
{ yyerror("ELSE must pair with IF");
$$ = 0; }
else
{ $$ = astnode_cons(ELSE, , , 0); } }
| '(' expr ')'
{ $$ = ; }
| ATOM
{ $$ = astnode_cons(ATOM, 0, 0, ); }
;
%%
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;
}
让我的 Yacc 坐起来乞求
我比以往任何时候都更加确信这里正确的方法是 GLR 语法，如果可能的话。然而，受@Kaz 的启发，我使用 LALR(1) 语法生成了以下 yacc/bison 语法（甚至没有使用优先级声明）。
当然，它作弊了，因为这个问题不能用 LALR(1) 文法来解决。在适当的时间间隔，它遍历 IF THEN 和 IF THEN ELSE 表达式的构造树，并根据需要移动 ELSE 子句。
需要重新检查可能运动的节点被赋予 AST 节点类型 IFSEQ 并且 ELSE 子句附加了传统的最紧密匹配语法，使用经典 matched-if/unmatched-if 语法。完全匹配的 IF THEN ELSE 子句不需要重新排列；树重写将应用于与右手操作数不匹配的第一个 ELSE 关联的表达式（如果有的话）。将 IF 表达式的完全匹配前缀与需要重新排列的尾部分开需要几乎重复一些规则；几乎重复的规则的不同之处在于它们的操作直接产生 TERNARY 个节点，而不是 IFSEQ 个节点。
为了正确回答问题，还需要重新排列一些 IFF 节点，因为 IFF 比 THEN 子句更弱，比 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 和将它们更改为 p -> q 和更改 THEN 的拼写。其他运算符将不会被解析，括号将被保留。然后它将生成的令牌流馈送到具有更传统语法样式的第二个 LALR 解析器。我可能会开始编写代码，只是因为我认为两次传递的 bison 解析器偶尔有用，而且周围几乎没有示例。
这是树重写解析器。对于长度，我深表歉意：
%{
#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(, stdout); putchar('\n'); node_free(); }
| '\n'
| error '\n'
term : T_ID { $$ = atom(); }
| "not" term { $$ = node(NEG, , NULL, NULL); }
| '(' expr ')' { $$ = ; }
conj : term
| conj "and" term { $$ = node(CONJ, , , NULL); }
disj : conj
| disj "or" conj { $$ = node(DISJ, , , NULL); }
bicond: disj
| disj "iff" bicond { $$ = node(BICOND, , , NULL); }
mat : bicond
| "if" expr "then" mat "else" mat
{ $$ = node(IFSEQ, , , ); }
unmat: "if" expr "then" mat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" mat "else" unmat
{ $$ = node(IFSEQ, , , ); }
tail : "if" expr "then" mat
{ $$ = node(IFSEQ, , , NULL); }
| "if" expr "then" unmat
{ $$ = node(IFSEQ, , , NULL); }
cond : bicond
| tail { shift_elses($$, build_else_stack($$, NULL)); }
| "if" expr "then" mat "else" cond
{ $$ = node(TERNARY, , , ); }
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, "%s\n", 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;}
如所写，parser/lexer 一次读取一行，并为每一行打印 AST（因此不允许使用多行表达式）。我希望清楚如何更改它。