各位大虾，小弟有难啊！

Monox

回复 26# felonwan

语法树不一定是二叉树，不过一般二叉树就够用了，特别是对这个例子来说。事实上用正则处理的过程本质上也是进行词法和语法分析，只不过因为没有中间建立语法树的过程，所以代码的维护和扩展会比较麻烦，毕竟词法语法和语义方面的代码全混杂在一起嘛。
   

Monox

回复 30# MMMIX

嗯，这个我赞同。如果不考虑效率的话（这个我一般最后考虑），处理一般的任务都是像Perl,Ruby之类的动态脚本语言比C简单。所以我才在这里贴出这个方案的，希望有其他人写，原本我自己没打算要给代码的，因为我自己现在工作中用不到Perl，而作为兴趣的话比起Perl我更喜欢Haskell(虽然才刚入门)，所以自己写的话会用Haskell或C写，不过又不知道这个论坛的人会不会对这两种语言的实现感兴趣。像这种简单的语法分析工作，确实用手工写DFA实现就够了，不过之所以提Flex和YACC，以及Haskell的parsec，是因为使用这些工具就是熟悉这些工具的过程，然后我在其它更复杂一些的项目里就可以更加得心应手的用它们了（虽然事实上我已经使用过这些工具了，包括在公司的一个小项目上）。而，相对的，另一方面，虽然我知道纯手工写DFA实现词法和语法分析的算法，但是因为我并不是计算机相关专业毕业，所有这些都是我自学的，所以没有过什么课堂作业之类，也就从来没有真正手工写过，所以我也想尝试一次，所以在22楼我说了，如果我有时间的话，会用四种方式（原贴错打成三种了）来实现，其中就包括纯手工用C和Perl来写。

sars318

顶，interact inside 和or各写一个函数

MMMIX

Monox 发表于 2013-12-24 13:58
回复 30# MMMIX
像这种简单的语法分析工作，确实用手工写DFA实现就够了

DFA是用来做词法分析的，可是像楼主这里的表达式，哪里用得上DFA，Perl 的 split 就足够了。

Monox

回复 34# MMMIX

DFA除了可以做词法分析，也可以用来做语法分析，对LR（0）文法的分析栈，不过我还不确定楼主这个是否一定属于LR(0)文法。另外，我真用Perl写这个的话，还不确定会有什么方式进行词法分析，可能一个字符一个字符扫描，用DFA的方式来实现，也可能用正则，但是肯定不会用split，理由还是跟之前说的一样我的关注点并不是楼主问题的解（这个留给其他人了，事实上已经有很多人尝试给解了，虽然我没去具体看那些解），仅仅是出于个人兴趣用另一种更通用，可以扩展的方式来实现楼主这个问题，没准之后会被我当作一下小型语言解释器的代码框架进行修改和扩充。
   

yuanquan08

回复 35# Monox

期待楼上

   

MMMIX

回复 35# Monox


    一般的词法分析肯定少不了逐个字符的扫描。不过在特殊情况下，例如楼主这里的表达式，split 就完全足够了。

MMMIX

回复 1# yuanquan08


    解析表达式构造语法树，对语法树求值得出结果：

1. 
   
2. #!/usr/bin/perl
   
3. 
   
4. use strict;
   
5. use warnings;
   
6. 
   
7. use feature "switch";
   
8. 
   
9. use Data::Dumper;
   
10. 
    
11. my @tokens;
    
12. my %operators = (
    
13.         'interact'        => 1,
    
14.         'inside'        => 1,
    
15.         'or'                => 1,
    
16. );
    
17. 
    
18. while (my $exp = <DATA>) {
    
19.         @tokens = map { $_ ? $_ : () } split(/\s*([\(\)])\s*|\s+/, $exp);
    
20.         my $syn_tree = parser();
    
21. 
    
22.         print $exp;
    
23.         print Dumper($syn_tree), "\n";
    
24.         print Dumper(evaluate($syn_tree)), "\n";
    
25. }
    
26. 
    
27. sub evaluate {
    
28.         my $tree = shift;
    
29. 
    
30.         if (ref($tree) ne "HASH") {
    
31.                 return ($tree);
    
32.         }
    
33. 
    
34.         given ($tree->{op}) {
    
35.                 when (/or/) {
    
36.                         return (evaluate($tree->{left}), evaluate($tree->{right}));
    
37.                 }
    
38.                 when (/interact|inside/) {
    
39.                         my @left = evaluate($tree->{left});
    
40.                         my @right = evaluate($tree->{right});
    
41.                         my @result;
    
42.                         foreach my $l (@left) {
    
43.                                 foreach my $r (@right) {
    
44.                                         push @result, "${l}_${r}";
    
45.                                 }
    
46.                         }
    
47.                         return @result;
    
48.                 }
    
49.         }
    
50. }
    
51. 
    
52. sub parser {
    
53.         my ($left, $op, $right);
    
54. 
    
55.         while (@tokens) {
    
56.                 my $token = shift @tokens;
    
57.                 given ($token) {
    
58.                         when (is_variable($token)) {
    
59.                                 if (not $left) {
    
60.                                         $left = $token;
    
61.                                 } elsif ($left and $op) {
    
62.                                         my $node = node($op, $left, $token);
    
63.                                         if (@tokens) {
    
64.                                                 if ($tokens[0] =~ /\)/) {
    
65.                                                         $right = $token;
    
66.                                                 } else {
    
67.                                                         $left = $node;
    
68.                                                         $op = undef;
    
69.                                                 }
    
70.                                         } else {
    
71.                                                 return $node;
    
72.                                         }
    
73.                                 } else {
    
74.                                         die "Syntax error!";
    
75.                                 }
    
76.                         }
    
77.                         when (is_operator($token)) {
    
78.                                 if ($left) {
    
79.                                         $op = $token;
    
80.                                 } else {
    
81.                                         die "Syntax error!";
    
82.                                 }
    
83.                         }
    
84.                         when (/\(/) {
    
85.                                 if (not $left) {
    
86.                                         $left = parser();
    
87.                                         if (not @tokens) {
    
88.                                                 return $left;
    
89.                                         }
    
90.                                 } elsif ($left and $op) {
    
91.                                         return node($op, $left, parser());
    
92.                                 } else {
    
93.                                         die "Syntax error!";
    
94.                                 }
    
95.                         }
    
96.                         when (/\)/) {
    
97.                                 if ($right) {
    
98.                                         return node($op, $left, $right);
    
99.                                 } elsif ($left and not $op) {
    
100.                                         return $left;
     
101.                                 }
     
102.                                 else {
     
103.                                         die "Syntax error!";
     
104.                                 }
     
105.                         }
     
106.                 }
     
107.         }
     
108. }
     
109. 
     
110. sub is_variable {
     
111.         my $token = shift;
     
112.         $token =~ /[[:upper:]]/;
     
113. }
     
114. 
     
115. sub is_operator {
     
116.         my $token = shift;
     
117. 
     
118.         $operators{$token};
     
119. }
     
120. 
     
121. sub node {
     
122.         my ($op, $left, $right) = @_;
     
123.         return {
     
124.                 'left'        => $left,
     
125.                 'op'        => $op,
     
126.                 'right'        => $right,
     
127.         };
     
128. }
     
129. 
     
130. 
     
131. __DATA__
     
132. A or B
     
133. A or B or C
     
134. (A or B)
     
135. ((A or B) or C)
     
136. (A or (B or C))
     
137. (A interact  ((B  or  C)  or (((D inside E) or F)  inside G)))
     

复制代码

MMMIX

回复 12# yuanquan08


    添加对 not 的支持：

1. 
   
2. #!/usr/bin/perl
   
3. 
   
4. use strict;
   
5. use warnings;
   
6. 
   
7. use feature "switch";
   
8. 
   
9. use Data::Dumper;
   
10. 
    
11. my @tokens;
    
12. my %operators = (
    
13.         'interact'        => 1,
    
14.         'inside'        => 1,
    
15.         'or'                => 1,
    
16.         'not'                => 1,
    
17. );
    
18. 
    
19. while (my $exp = <DATA>) {
    
20.         @tokens = map { $_ ? $_ : () } split(/\s*([\(\)])\s*|\s+/, $exp);
    
21.         my $syn_tree = parser();
    
22. 
    
23.         print $exp;
    
24.         print Dumper($syn_tree), "\n";
    
25.         print Dumper(evaluate($syn_tree)), "\n";
    
26. }
    
27. 
    
28. sub evaluate {
    
29.         my $tree = shift;
    
30. 
    
31.         if (ref($tree) ne "HASH") {
    
32.                 return ($tree);
    
33.         }
    
34. 
    
35.         given ($tree->{op}) {
    
36.                 when (/or/) {
    
37.                         return (evaluate($tree->{left}), evaluate($tree->{right}));
    
38.                 }
    
39.                 when (/not .+/) {
    
40.                         return (evaluate($tree->{left}));
    
41.                 }
    
42.                 when (/interact|inside/) {
    
43.                         my @left = evaluate($tree->{left});
    
44.                         my @right = evaluate($tree->{right});
    
45.                         my @result;
    
46.                         foreach my $l (@left) {
    
47.                                 foreach my $r (@right) {
    
48.                                         push @result, "${l}_${r}";
    
49.                                 }
    
50.                         }
    
51.                         return @result;
    
52.                 }
    
53.         }
    
54. }
    
55. 
    
56. sub parser {
    
57.         my ($left, $op, $right);
    
58. 
    
59.         while (@tokens) {
    
60.                 my $token = shift @tokens;
    
61.                 given ($token) {
    
62.                         when (is_variable($token)) {
    
63.                                 if (not $left) {
    
64.                                         $left = $token;
    
65.                                 } elsif ($left and $op) {
    
66.                                         my $node = node($op, $left, $token);
    
67.                                         if (@tokens) {
    
68.                                                 if ($tokens[0] =~ /\)/) {
    
69.                                                         $right = $token;
    
70.                                                 } else {
    
71.                                                         $left = $node;
    
72.                                                         $op = undef;
    
73.                                                 }
    
74.                                         } else {
    
75.                                                 return $node;
    
76.                                         }
    
77.                                 } else {
    
78.                                         die "Syntax error!";
    
79.                                 }
    
80.                         }
    
81.                         when (is_operator($token)) {
    
82.                                 if ($token =~ /not/) {
    
83.                                         if (@tokens and is_operator($tokens[0])) {
    
84.                                                 $token = join(' ', $token, shift @tokens);
    
85.                                         } else {
    
86.                                                 die "Syntax error!";
    
87.                                         }
    
88.                                 }
    
89. 
    
90.                                 if ($left) {
    
91.                                         $op = $token;
    
92.                                 } else {
    
93.                                         die "Syntax error!";
    
94.                                 }
    
95.                         }
    
96.                         when (/\(/) {
    
97.                                 if (not $left) {
    
98.                                         $left = parser();
    
99.                                         if (not @tokens) {
    
100.                                                 return $left;
     
101.                                         }
     
102.                                 } elsif ($left and $op) {
     
103.                                         return node($op, $left, parser());
     
104.                                 } else {
     
105.                                         die "Syntax error!";
     
106.                                 }
     
107.                         }
     
108.                         when (/\)/) {
     
109.                                 if ($right) {
     
110.                                         return node($op, $left, $right);
     
111.                                 } elsif ($left and not $op) {
     
112.                                         return $left;
     
113.                                 }
     
114.                                 else {
     
115.                                         die "Syntax error!";
     
116.                                 }
     
117.                         }
     
118.                 }
     
119.         }
     
120. }
     
121. 
     
122. sub is_variable {
     
123.         my $token = shift;
     
124.         $token =~ /[[:upper:]]/;
     
125. }
     
126. 
     
127. sub is_operator {
     
128.         my $token = shift;
     
129. 
     
130.         $operators{$token};
     
131. }
     
132. 
     
133. sub node {
     
134.         my ($op, $left, $right) = @_;
     
135.         return {
     
136.                 'left'        => $left,
     
137.                 'op'        => $op,
     
138.                 'right'        => $right,
     
139.         };
     
140. }
     
141. 
     
142. 
     
143. __DATA__
     
144. A or B
     
145. A or B or C
     
146. (A or B)
     
147. ((A or B) or C)
     
148. (A or (B or C))
     
149. (A not inside B)
     
150. (A interact  ((B  or  C)  or (((D inside E) or F)  inside G)))
     
151. (A interact  ((B  or  C)  or (((D inside E) or F)   not   inside G)))
     

复制代码

yinyuemi

回复 38# MMMIX

牛啊！非常棒的语法解析~