如何設計文法的語義子程序？

01-23

RT

題主說的「語義子程序」是指「語義動作」（semantic action）吧？語法指導翻譯（syntax-directed translation）的概念。那好辦啊。

首先題主給的題目的語法是：

E -&> E + T | E ? T | T


T -&> T * F

   | T ? F

   | F

F -&> num | bool | ( E )

那對應的類型檢查語義動作可以如下偽代碼。類型檢查中，「類型」是一種「合成屬性」（synthesized attribute），屬性從規則右邊流向規則左邊。

為了方便標記，給同一規則中重複出現的符號標個號：

E -&> E1 + T { if (E1.type != num || T.type != num) error(); E.type = num; } | E1 ? T { if (E1.type != bool || T.type != bool) error(); E.type = bool; } | T { E.type = T.type; }


T -&> T1 * F  { if (T1.type != num || F.type != num)

                 error();

               T.type = num;

             }

   | T1 ? F  { if (T1.type != bool || F.type != bool)

                 error();

               T.type = bool;

             }

   | F       { T.type = F.type; }

F -&> num { F.type = num; } | bool { F.type = bool; } | ( E ) { F.type = E.type; }

同理，要翻譯為逆波蘭表達式如下：

E -&> E1 + T { print("+"); } | E1 ? T { print("?"); } | T


T -&> T1 * F  { print("*"); }

   | T1 ? F  { print("?"); }

   | F

F -&> num { print(num.lexval); } | bool { print(bool.lexval); } | ( E )

題主要做的就是把上面兩者結合在一起然後用題目要求的代碼形式寫出來就好了。

寫完了，一直提交不了，總是提示，出錯了，請稍後再試！一刷新草稿都沒了！！！

什麼破玩意兒，輸入JavaCC代碼，就提示沒法提交，刪掉就可以？？？/

===================================================

你給的這段BNF文法其實是C系列語言的表達式文法的子集。

這個題目如果使用實際的語法分析器的生成器來做就很好做了，直接弄成相應的代碼即可。

由工具自動生成對應的解析代碼，比如：C/C++語言系的lex/bison，Java語言系的JavaCC。

此處我就按照JavaCC的語法來了。為了避免左遞歸，我把你的文法直接修改成以下形式。

E -&> T + E | T ? E | T


T -&> F * T

   | F ? T

   | F

F -&> num | bool | ( E )

在你給的文法BNF中，所有的大寫字母都表示非終結符，如E，T，F。按照 @RednaxelaFX R大的回答，所有的非終結符都擁有type這樣的屬性，表明這個表達式的類型。表現在在代碼裡面就是每個非終結符都對應一個AST類，這個類有一個type屬性（或者成員變數）表示它的類型，當前為了簡單，可以直接用字元串表示，如："int"，"bool"等。然後，觀察我給的BNF文法中，主要有兩類AST，一類是終結符，如整數字面量，bool型字面量。另外一類是二元運算符構成的表達式。

那麼就是兩類AST類，一個是BinaryOperator類，一種是IntegralLiteral，BooleanLiteral。對於(E)可以直接使用E的AST，不影響結果，因為不追求AST dump的精確性。

enum TypeClass { Integral, Bool }


public abstract class Expr

{

	TypeClass tc;

	public Expr(TypeClass tc)

	{

		this.tc = tc;

	}

	 // 將該AST樹列印成逆波蘭式。

	public abstract void print();

}

public class BinaryOperator extends Expr

{

	Expr lhs, rhs;

	char opcode;

	public BinaryOperator(TypeClass tc, Expr lhs, Expr rhs, char opcode)

	{

		super(tc);

		this.lhs = lhs;

		this.rhs = rhs;

		this.opcode = opcode;

	}
	// 將該AST樹列印成逆波蘭式。

	public void print()

	{

	  lhs.print();

	  rhs.print();

	  System.out.print(opcode);

	}

}
public class IntegralLiteral extends Expr

{

	int literal;

	public IntegralLiteral(TypeClass tc, int lit)

	{

		super(tc);

		literal = lit;

	}
	// 將該AST樹列印成逆波蘭式。

	public void print()

	{

	  System.out.print(literal);

	}

}
public class BooleanLiteral extends Expr

{

	boolean literal;

	public BooleanLiteral(TypeClass tc, boolean lit)

	{

		super(tc);

		literal = lit;

	}

// 將該AST樹列印成逆波蘭式。 public void print() { System.out.print(literal); } }

JavaCC代碼如下

// Parser.jj 文件 options { // 控制JavaCC接受unicode編碼。 JAVA_UNICODE_ESCAPE = true; }


PARSER_BEGIN(Parser)
// 生成的Parser名稱

public class Parser {
}
PARSER_END(Parser)
// 跳過空白符

SKIP : /* WHITE SPACE */

{

  " "

| "	"

| "

"

| "

"

| "f"

}

// 整數字面量

TOKEN : /* LITERALS */

{

  &< INTEGER_LITERAL:
        & (["l","L"])?

      | & (["l","L"])?

      | & (["l","L"])?

  &>

|

  &< #DECIMAL_LITERAL: ["1"-"9"] (["0"-"9"])* &>

|

  &< #HEX_LITERAL: "0" ["x","X"] (["0"-"9","a"-"f","A"-"F"])+ &>

|

  &< #OCTAL_LITERAL: "0" (["0"-"7"])* &>

}
// E非終結符的處理函數

Expr E() :

{Expr lhs, rhs;}

{

  lhs = T();

  "+"

  {

    rhs = E();

    if (lhs == null || rhs == null)

      return null;

    if (lhs.type != rhs.type || lhs.type != Integral)

      return error("The type of lhs is imcompatible with type of rhs!");

    return new BinaryOperator(Integral, lhs, rhs, "+");

  }

  |

  "V"

  {

    rhs = E();

    if (lhs == null || rhs == null)

      return null;

    if (lhs.type != rhs.type || lhs.type != Integral)

      return error("The type of lhs is imcompatible with type of rhs!");

    return new BinaryOperator(Integral, lhs, rhs, "V");

  }

  | {return lhs;}

}
Expr T():

{Expr lhs, rhs;}

{

   lhs = F();

  "*"

  {

    rhs = T();

    if (lhs == null || rhs == null)

      return null;

    if (lhs.type != rhs.type || lhs.type != Integral)

      return error("The type of lhs is imcompatible with type of rhs!");

    return new BinaryOperator(Integral, lhs, rhs, "*");

  }

  |

  "^"   //交集運算符號打不出來

  {

    rhs = F();

    if (lhs == null || rhs == null)

      return null;

    if (lhs.type != rhs.type || lhs.type != Integral)

      return error("The type of lhs is imcompatible with type of rhs!");

    return new BinaryOperator(Integral, lhs, rhs, "^");

  }

  | {return lhs;}

}

Expr F(): { Expr result; Token; } { t = "true" {return new BooleanLiteral(Bool, true);} | t = "false" {return new BooleanLiteral(Bool, false);} | t = & {return new IntegralLiteral(Integral, Integer.parseInt(t.image));} | "(" result = E() ")" {return result;} }

然後調用Expr.print函數後序遍歷AST即可列印出逆波蘭式。