精华内容
下载资源
问答
  • 2018-05-31 08:17:38

    本人博客内编译原理文章的配套资源jar包,包括词法分析,语法分析,中间代码生成,静态语义检查,代码解释执行以及抽象语法树的手动生成:https://download.csdn.net/download/as1072966956/10448935

    转载请注明出处。


    程序要求能自动生成AST抽象语法树。

    Lab3Main.java

    package sch.cauc.edu.token;
    
    import edu.ustc.cs.compile.platform.interfaces.InterRepresent;
    /**
     * 
     * 
     * Lab3Main
     * 创建人:xrzhang 
     * 时间:2018年5月25日-上午8:13:05 
     * @version 1.0.0
     *
     */
    public class Lab3Main {
    
    	public static void main(String[] args) {
    		//String srcFileName="test/expr3.txt";
    		//String srcFileName="test/expr221.txt";
    		String srcFileName="test/expr222.txt";
    		//String srcFileName="test/testown.txt";
    		SyntaxDirectedTranslation parser=new SyntaxDirectedTranslation();
    		InterRepresent ir=parser.doParse(srcFileName);
    		ir.showIR();
    	}
    }
    

    SyntaxDirectedTranslation.java

    package sch.cauc.edu.token;
    import java.util.LinkedList;
    
    
    
    import org.eclipse.jdt.core.dom.*;
    import edu.ustc.cs.compile.platform.interfaces.InterRepresent;
    import edu.ustc.cs.compile.util.ir.HIRPack;
    
    public class SyntaxDirectedTranslation {
    	/*抽象语法树的根节点*/
    	private AST ast=null;
    	private BlockLexer lexer=null;
    	private Token lookAhead=null;
    	 public SyntaxDirectedTranslation() {
    		ast = AST.newAST(AST.JLS3);
    	}
    	 public InterRepresent doParse(String filePath){
    		 lexer=new BlockLexer(filePath);
    		 Block mainBody = this.parse();
    		 HIRPack ir = new HIRPack();
    		 ir.setIR(mainBody);
    		 return ir;
    	 }
    	 public Token matchToken(TokenType type,String functionName){
    		
    		 if(lookAhead.getType()!=type){
    			 parsingError(type.toString(),functionName);
    		 }
    		 Token matchedSymbol = lookAhead;
    		 lookAhead = lexer.nextToken();
    		 return matchedSymbol; 
    	 }
    	 public void parsingError(String types,String functionName){
    			System.out.println("Parsing Error! in"+functionName);
    			System.out.println("encounter "+lookAhead.getLexeme());
    			System.out.println("at line "+lookAhead.getLine()+",column "+lookAhead.getColumn());
    			System.out.println("while expecting "+types);
    			System.exit(1);
    		}
    	 /**
    	 * 
    	 * 调用开始符号对应的方法,进行语法分析
    	 * 方法名:parse
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-上午10:27:14 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	public Block parse() {
    		System.out.println("In parse();-----jmzhang-----");
    		lookAhead=lexer.nextToken();
    		Block mainBody=simpleblock();
    		System.out.println("Parsing Success!");
    		return mainBody;
    	}
    	/**
    	 * 
    	 * simpleblock = LBRACE sequence RBRACE
    	 * B->{S}
    	 * 方法名:simpleblock
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月19日-下午6:59:57 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	public  Block simpleblock() {
    		System.out.println("In simpleblock();-----jmzhang-----");
    		if(lookAhead.getType()==TokenType.LBRACKET){
    			matchToken(TokenType.LBRACKET, "simpleblock");
    			System.out.println("***********{*********");
    			LinkedList seq =sequence();
    			matchToken(TokenType.RBRACKET, "simpleblock");
    			System.out.println("***********}*********");
    			Block mainBody=ast.newBlock();
    			if (seq!=null) {
    				for(int i=0;i<seq.size();i++){
    					mainBody.statements().add(seq.get(i));
    				}
    			}
    			return mainBody;
    		}else{
    			parsingError(TokenType.LBRACKET.toString(), "simpleblock");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * sequence=assognmentStatement sequence |
    	 * 			ifStatement sequence |
    	 * 			whileStatement sequence |
    	 * 			epsilon
    	 * S->AS | IS |WS | ε
    	 * 方法名:Sequence
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午8:54:23 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private LinkedList sequence() {
    		System.out.println("In Sequence();-----jmzhang-----");
    		if(lookAhead.getType()==TokenType.IDENTIFIER){
    		
    			ExpressionStatement es=assignmentStatement();
    			LinkedList seq=sequence();
    			if (seq==null) {
    				seq=new LinkedList();
    				}
    			seq.addFirst(es);
    			return seq;
    		}else if (lookAhead.getType()==TokenType.KEY_IF) {
    			
    			IfStatement es=ifStatement();
    			LinkedList seq=sequence();
    			if (seq==null) {
    				seq=new LinkedList();
    				}
    			seq.addFirst(es);
    			return seq;
    		}else if (lookAhead.getType()==TokenType.KEY_WHILE) {
    			System.out.println("In Sequence();-----jmzhang-----WHILE");
    			WhileStatement es=whileStatement();
    			LinkedList seq=sequence();
    			if (seq==null) {
    				seq=new LinkedList();
    				}
    			seq.addFirst(es);
    			return seq;
    		}else if (lookAhead.getType()==TokenType.RBRACKET) {
    			//match epslon
    			return null;
    		}else {
    			String errorTypes=TokenType.IDENTIFIER.toString()+","+TokenType.RBRACKET.toString();
    			parsingError(errorTypes, "sequence");
    			return null;
    		}
    	}
    	/************************************>
    	 * @return ************************************/
    	
    	
    	
    	
    	
    	private WhileStatement whileStatement() {
    		System.out.println("In whileStatement();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.KEY_WHILE) {
    			matchToken(TokenType.KEY_WHILE, "whileStatement");
    			WhileStatement wStatement=ast.newWhileStatement();
    			
    			System.out.println("***********while*********");
    			matchToken(TokenType.LPAREN, "whileStatement");
    			System.out.println("***********(*********");
    			Expression be=Boolexpression();
    			wStatement.setExpression(be);
    			matchToken(TokenType.RPAREN, "whileStatement");
    			System.out.println("***********)*********");
    			matchToken(TokenType.LBRACKET, "whileStatement");
    			System.out.println("***********{*********");
    			
    			Block ifbody=ast.newBlock();
    			LinkedList seq =sequence();
    			if (seq!=null) {
    				for(int i=0;i<seq.size();i++){
    					ifbody.statements().add(seq.get(i));
    				}
    			}
    			wStatement.setBody(ifbody);
    			matchToken(TokenType.RBRACKET, "whileStatement");
    			System.out.println("***********}*********");
    			
    			/*if (seq!=null) {
    				for(int i=0;i<seq.size();i++){
    					mainBody.statements().add(seq.get(i));
    				}
    			}*/
    			return wStatement;
    		}else {
    			String errorTypes=TokenType.KEY_WHILE.toString();
    			parsingError(errorTypes, "whileStatement");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * 
    	 * 方法名:Boolexpression
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月19日-下午8:58:23 
    	 * 邮件:jmzhang_15_cauc@163.com
    	 * @return Expression
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression Boolexpression() {
    		System.out.println("In Boolexpression();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.BOOL_TRUE
    				||lookAhead.getType()==TokenType.BOOL_FALSE
    				||lookAhead.getType()==TokenType.LPAREN
    				||lookAhead.getType()==TokenType.IDENTIFIER
    				||lookAhead.getType()==TokenType.INTEGER_LITERAL) {
    			InfixExpression infix=ast.newInfixExpression();
    			
    			Expression left=Boolterm();
    			Expression right=Boolexpression_1(left);
    			return right;
    		}else {
    			String errorTypes =TokenType.BOOL_TRUE.toString()
    					+","+TokenType.BOOL_FALSE.toString()
    					+","+TokenType.LPAREN.toString()
    					+","+TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString();
    			parsingError(errorTypes, "Boolexpression");
    			return null;
    		}	
    	}
    	/**
    	 * 
    	 * 方法名:Boolexpression_1
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月19日-下午9:02:26 
    	 * 邮件:jmzhang_15_cauc@163.com
    	 * @param left
    	 * @return Expression
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression Boolexpression_1(Expression left) {
    		System.out.println("In Boolexpression_1();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.LOGICAL_OR) {
    			matchToken(TokenType.LOGICAL_OR, "Boolexpression_1");
    			System.out.println("***********||*********");
    			Expression right=Boolterm();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression e=Boolexpression_1(infixEx);
    			return e;
    		}else if (lookAhead.getType()==TokenType.RPAREN) {
    			//match epslin
    			//follow(E')={')',','}
    			return left;
    		}else {
    			String errorTypes =TokenType.LOGICAL_OR.toString()
    					+","+TokenType.RPAREN.toString();
    			parsingError(errorTypes, "Boolexpression_1");
    			return null;
    		}	
    	}
    	/**
    	 * 
    	 * 方法名:Boolterm
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月19日-下午9:03:36 
    	 * 邮件:jmzhang_15_cauc@163.com
    	 * @return Expression
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression Boolterm() {
    		System.out.println("In Boolterm();-----jmzhang-----");
    		if(lookAhead.getType()==TokenType.BOOL_TRUE
    				||lookAhead.getType()==TokenType.BOOL_FALSE
    				||lookAhead.getType()==TokenType.LPAREN
    				||lookAhead.getType()==TokenType.IDENTIFIER
    				||lookAhead.getType()==TokenType.INTEGER_LITERAL){
    			Expression f=Boolfactor();
    			Expression t=Boolterm_1(f);
    			return t;
    		}else {
    			String errorTypes =TokenType.BOOL_TRUE.toString()
    					+","+TokenType.BOOL_FALSE.toString()
    					+","+TokenType.LPAREN.toString()
    					+","+TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString();
    			parsingError(errorTypes, "Boolterm");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * 方法名:Boolterm_1
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月19日-下午9:08:20 
    	 * 邮件:jmzhang_15_cauc@163.com
    	 * @param left
    	 * @return Expression
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression Boolterm_1(Expression left) {
    		System.out.println("In Boolterm_1();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.LOGICAL_AND) {
    			matchToken(TokenType.LOGICAL_AND, "Boolterm_1");
    			System.out.println("***********&&*********");
    			Expression right=Boolfactor();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setOperator(InfixExpression.Operator.AND);
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression t=Boolterm_1(infixEx);
    			return t;
    		}else if (lookAhead.getType()==TokenType.LOGICAL_OR
    				||lookAhead.getType()==TokenType.RPAREN) {
    			//match e[slion
    			//follow(T')={'+','-',')',',')
    			return left;
    		}else {
    			String errorTypes =TokenType.LOGICAL_AND.toString()
    					+","+TokenType.LOGICAL_OR.toString()
    					+","+TokenType.RPAREN.toString();
    			parsingError(errorTypes, "Boolterm_1");
    			return null;
    		}
    		
    		
    	}
    
    	private Expression Boolfactor() {
    		System.out.println("In Boolfactor();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.BOOL_TRUE) {
    			Token id=matchToken(TokenType.BOOL_TRUE, "Boolfactor");
    			System.out.println("***********true*********");
    			SimpleName sn=ast.newSimpleName(id.getLexeme());
    			return sn;
    			
    		}else if (lookAhead.getType()==TokenType.BOOL_FALSE) {
    			
    			Token num=matchToken(TokenType.BOOL_FALSE, "Boolfactor");
    			System.out.println("***********flase*********");
    			NumberLiteral nl=ast.newNumberLiteral(num.getLexeme());
    			return nl;
    		}else if (lookAhead.getType()==TokenType.LPAREN||
    				lookAhead.getType()==TokenType.IDENTIFIER||
    				lookAhead.getType()==TokenType.INTEGER_LITERAL){
    			Expression r=relationlExpression();
    			return r;
    		}else {
    			String errorTypes =TokenType.BOOL_TRUE.toString()
    					+","+TokenType.BOOL_FALSE.toString()
    					+","+TokenType.LPAREN.toString()
    					+","+TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString();
    			parsingError(errorTypes, "relationlExpressionOperator");
    			return null;
    		}		
    	}
    
    	private Expression relationlExpression() {
    		System.out.println("In relationlExpression();-----jmzhang-----");
    		
    		if (lookAhead.getType()==TokenType.LPAREN||
    				lookAhead.getType()==TokenType.IDENTIFIER||
    				lookAhead.getType()==TokenType.INTEGER_LITERAL) {
    			InfixExpression infix=ast.newInfixExpression();
    			Expression left=expression();
    			infix.setLeftOperand(left);
    			//Expression r=relationlExpressionOperator();
    			infix.setOperator(relationlExpressionOperator());
    			Expression right=expression();
    			infix.setRightOperand(right);
    			return infix;
    		}else {
    			String errorTypes =TokenType.LPAREN.toString()
    					+","+TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString();
    			parsingError(errorTypes, "relationlExpression");
    			return null;
    		}
    	}
    
    	private InfixExpression.Operator relationlExpressionOperator() {
    		System.out.println("In relationlExpressionOperator();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.LESS) {
    			matchToken(TokenType.LESS, "relationlExpressionOperator");
    			System.out.println("***********<*********");
    			return InfixExpression.Operator.LESS;
    		}else if (lookAhead.getType()==TokenType.GREATER) {
    			matchToken(TokenType.GREATER, "relationlExpressionOperator");
    			System.out.println("***********>*********");
    			return InfixExpression.Operator.GREATER;
    		}else if (lookAhead.getType()==TokenType.LESS_EQUAL) {
    			matchToken(TokenType.LESS_EQUAL, "relationlExpressionOperator");
    			System.out.println("***********<=*********");
    			return InfixExpression.Operator.LESS_EQUALS;
    		}else if (lookAhead.getType()==TokenType.GREATER_EQUAL) {
    			matchToken(TokenType.GREATER_EQUAL, "relationlExpressionOperator");
    			System.out.println("***********>=*********");
    			return InfixExpression.Operator.GREATER_EQUALS;
    		}else if (lookAhead.getType()==TokenType.NOT_EQUAL) {
    			matchToken(TokenType.NOT_EQUAL, "relationlExpressionOperator");
    			System.out.println("***********!=*********");
    			return InfixExpression.Operator.NOT_EQUALS;
    		}else if(lookAhead.getType()==TokenType.EQUAL) {
    			matchToken(TokenType.EQUAL, "relationlExpressionOperator");
    			System.out.println("***********==*********");
    			return InfixExpression.Operator.EQUALS;
    		}else {
    			String errorTypes =TokenType.LESS.toString()
    					+","+TokenType.GREATER.toString()
    					+","+TokenType.LESS_EQUAL.toString()
    					+","+TokenType.GREATER_EQUAL.toString()
    					+","+TokenType.NOT_EQUAL.toString()
    					+","+TokenType.EQUAL.toString();
    			parsingError(errorTypes, "relationlExpressionOperator");
    			return null;
    		}
    	}
    
    	private IfStatement ifStatement() {
    		System.out.println("In ifStatement();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.KEY_IF) {
    			
    			matchToken(TokenType.KEY_IF, "ifStatement");
    			IfStatement is = ast.newIfStatement();
    			System.out.println("***********if*********");
    			matchToken(TokenType.LPAREN, "ifStatement");
    			System.out.println("***********(*********");
    			
    			Expression be=Boolexpression();
    			is.setExpression(be);
    			matchToken(TokenType.RPAREN, "ifStatement");
    			System.out.println("***********)*********");
    			matchToken(TokenType.LBRACKET, "ifStatement");
    			System.out.println("***********{*********");
    			
    			Block ifbody=ast.newBlock();
    			LinkedList seq =sequence();
    			if (seq!=null) {
    				for(int i=0;i<seq.size();i++){
    					ifbody.statements().add(seq.get(i));
    				}
    			}
    			
    			is.setThenStatement(ifbody);
    			matchToken(TokenType.RBRACKET, "ifStatement");
    			System.out.println("***********}*********");
    			if(lookAhead.getType()==TokenType.KEY_ELSE)
    			{
    				
    				Block o=OptionalElse();
    				is.setElseStatement(o);
    			}
    			return is;
    		}else {
    			String errorTypes=TokenType.KEY_IF.toString();
    			parsingError(errorTypes, "ifStatement");
    			return null;
    		}
    	}
    
    	private Block OptionalElse() {
    		System.out.println("In OptionalElse();-----jmzhang-----");
    		if(lookAhead.getType()==TokenType.KEY_ELSE){
    			System.out.println("In OptionalElse();-----jmzhang-----1");
    			matchToken(TokenType.KEY_ELSE, "OptionalElse");
    			IfStatement elIfStatement =ast.newIfStatement();
    			System.out.println("***********else*********");
    			matchToken(TokenType.LBRACKET, "OptionalElse");
    			System.out.println("***********{*********");
    			Block ifbody=ast.newBlock();
    			LinkedList seq =sequence();
    			if (seq!=null) {
    				for(int i=0;i<seq.size();i++){
    					ifbody.statements().add(seq.get(i));
    				}
    			}
    			
    			
    		
    			
    			matchToken(TokenType.RBRACKET, "OptionalElse");
    			System.out.println("***********}*********");
    			return ifbody;
    		}else if (lookAhead.getType()==TokenType.RBRACKET
    				||lookAhead.getType()==TokenType.KEY_IF
    				||lookAhead.getType()==TokenType.KEY_WHILE
    				||lookAhead.getType()==TokenType.IDENTIFIER) {
    			//match epslion
    			return null;
    		}else {
    			String errorTypes =TokenType.KEY_ELSE.toString()
    					+","+TokenType.RBRACKET.toString()
    					+","+TokenType.KEY_IF.toString()
    					+","+TokenType.KEY_WHILE.toString()
    					+","+TokenType.IDENTIFIER.toString();
    			parsingError(errorTypes, "OptionalElse");
    			return null;
    		}
    		
    	}
    	
    	
    	
    	
    	
    	
    	
    	
    	
    	/*************************************<**********************************/
    	/**
    	 * 
    	 * assignmentStatement =IDENTIFIER ASSIGN expression SEMICOLON
    	 * A->id = E;
    	 * 方法名:assignmentStatement
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午8:56:26 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private ExpressionStatement assignmentStatement() {
    		System.out.println("In assignmentStatement();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.IDENTIFIER) {
    			
    			Token id =matchToken(TokenType.IDENTIFIER, "assignmentStatement");
    			System.out.println("***********id*********");
    			matchToken(TokenType.ASSIGN, "assignmentStatement");
    			System.out.println("***********=*********");
    			Expression e=expression();
    			matchToken(TokenType.SEMICOLON, "assignmentStatement");
    			System.out.println("***********;*********");
    			SimpleName sn=ast.newSimpleName(id.getLexeme());
    			Assignment assign=ast.newAssignment();
    			assign.setLeftHandSide(sn);
    			assign.setOperator(Assignment.Operator.ASSIGN);
    			assign.setRightHandSide(e);
    			ExpressionStatement es=ast.newExpressionStatement(assign);
    			return es;
    		}else {
    			String errorTypes=TokenType.IDENTIFIER.toString();
    			parsingError(errorTypes, "assignmentStatement");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * expression = term expression_1
    	 * E->TE'
    	 * 方法名:expression
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午9:00:40 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression expression() {
    		System.out.println("In expression();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.IDENTIFIER
    				||lookAhead.getType()==TokenType.LPAREN
    				||lookAhead.getType()==TokenType.INTEGER_LITERAL) {
    			Expression left=term();
    			Expression right=expression_1(left);
    			return right;
    		}else {
    			String errorTypes =TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString()
    					+","+TokenType.LPAREN.toString();
    			parsingError(errorTypes, "expression");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * expression_1=PLUS term expression_1 | MINUS term expression_1 | epslin
    	 * E'->TE' | -TE' | ε
    	 * 方法名:expression_1
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午9:06:26 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression expression_1(Expression left) {
    		System.out.println("In expression_1();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.PLUS) {
    			matchToken(TokenType.PLUS, "expression_1");
    			System.out.println("***********+*********");
    			Expression right=term();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			
    			Expression e=expression_1(infixEx);
    			return e;
    		}else if (lookAhead.getType()==TokenType.MINUS) {
    			
    			matchToken(TokenType.MINUS, "expression_1");
    			System.out.println("***********-*********");
    			Expression right=term();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setOperator(InfixExpression.Operator.MINUS);
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression e=expression_1(infixEx);
    			return e;
    		}else if (lookAhead.getType()==TokenType.SEMICOLON
    				||lookAhead.getType()==TokenType.LESS
    				||lookAhead.getType()==TokenType.GREATER
    				||lookAhead.getType()==TokenType.LESS_EQUAL
    				||lookAhead.getType()==TokenType.GREATER_EQUAL
    				||lookAhead.getType()==TokenType.NOT_EQUAL
    				||lookAhead.getType()==TokenType.EQUAL
    				||lookAhead.getType()==TokenType.LOGICAL_AND
    				||lookAhead.getType()==TokenType.LOGICAL_OR
    				||lookAhead.getType()==TokenType.RPAREN) {
    			System.out.println("In expression_1();-----jmzhang-----follow");
    			//match epslin
    			//follow(E')={')',','}
    			return left;
    		}else {
    			System.out.println("In expression_1();-----jmzhang-----else");
    			String errorTypes =TokenType.PLUS.toString()
    					+","+TokenType.MINUS.toString()
    					+","+TokenType.SEMICOLON.toString()
    					+","+TokenType.LESS.toString()
    					+","+TokenType.GREATER.toString()
    					+","+TokenType.LESS_EQUAL.toString()
    					+","+TokenType.GREATER_EQUAL.toString()
    					+","+TokenType.NOT_EQUAL.toString()
    					+","+TokenType.EQUAL.toString();
    			parsingError(errorTypes, "expression_1");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * term=factor term_1
    	 * T->FT'
    	 * 方法名:term
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午9:16:51 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression term() {
    		System.out.println("In term();-----jmzhang-----");
    		if(lookAhead.getType()==TokenType.IDENTIFIER
    				||lookAhead.getType()==TokenType.LPAREN
    				||lookAhead.getType()==TokenType.INTEGER_LITERAL){
    			Expression f=factor();
    			Expression t=term_1(f);
    			return t;
    		}else {
    			String errorTypes =TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString()
    					+","+TokenType.LPAREN.toString();
    			parsingError(errorTypes, "term");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * term_1=MULT factor term_1 | DIV factor term_1 | MOD factor term_1 | epslin
    	 * T'->*FT' | /FT' |%FT'|ε
    	 * 方法名:term_1
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午9:20:00 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression term_1(Expression left) {
    		System.out.println("In term_1();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.TIMES) {
    			matchToken(TokenType.TIMES, "term_1");
    			System.out.println("***********乘*********");
    			Expression right=factor();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setOperator(InfixExpression.Operator.TIMES);
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression t=term_1(infixEx);
    			return t;
    		}else if (lookAhead.getType()==TokenType.DIVIDE) {
    			matchToken(TokenType.DIVIDE, "term_1");
    			System.out.println("***********/*********");
    			Expression right=factor();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setOperator(InfixExpression.Operator.DIVIDE);
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression t=term_1(infixEx);
    			return t;
    		}else if (lookAhead.getType()==TokenType.REMAINDER) {
    			matchToken(TokenType.REMAINDER, "term_1");
    			System.out.println("***********%*********");
    			Expression right=factor();
    			InfixExpression infixEx=ast.newInfixExpression();
    			infixEx.setOperator(InfixExpression.Operator.REMAINDER);
    			infixEx.setLeftOperand(left);
    			infixEx.setRightOperand(right);
    			Expression t=term_1(infixEx);
    			return t;
    		}else if (lookAhead.getType()==TokenType.PLUS
    				||lookAhead.getType()==TokenType.MINUS
    				||lookAhead.getType()==TokenType.RPAREN
    				||lookAhead.getType()==TokenType.SEMICOLON
    				||lookAhead.getType()==TokenType.LESS
    				||lookAhead.getType()==TokenType.GREATER
    				||lookAhead.getType()==TokenType.LESS_EQUAL
    				||lookAhead.getType()==TokenType.GREATER_EQUAL
    				||lookAhead.getType()==TokenType.NOT_EQUAL
    				||lookAhead.getType()==TokenType.EQUAL
    				||lookAhead.getType()==TokenType.LOGICAL_AND
    				||lookAhead.getType()==TokenType.LOGICAL_OR
    				||lookAhead.getType()==TokenType.RPAREN) {
    			//match e[slion
    			//follow(T')={'+','-',')',',')
    			return left;
    		}else {
    			String errorTypes =TokenType.TIMES.toString()
    					+","+TokenType.DIVIDE.toString()
    					+","+TokenType.REMAINDER.toString()
    					+","+TokenType.PLUS.toString()
    					+","+TokenType.MINUS.toString()
    					+","+TokenType.SEMICOLON.toString()
    					+","+TokenType.LESS.toString()
    					+","+TokenType.GREATER.toString()
    					+","+TokenType.LESS_EQUAL.toString()
    					+","+TokenType.GREATER_EQUAL.toString()
    					+","+TokenType.NOT_EQUAL.toString()
    					+","+TokenType.EQUAL.toString()
    					+","+TokenType.LOGICAL_AND.toString()
    					+","+TokenType.LOGICAL_OR.toString();
    			parsingError(errorTypes, "term_1");
    			return null;
    		}
    	}
    	/**
    	 * 
    	 * factor = LPAREN expression RPAREN | IDENTIFER|INTEGER_LITERAL
    	 * F->(E)|id| number
    	 * 方法名:factor
    	 * 创建人:xrzhang 
    	 * 时间:2018年5月16日-下午9:29:47 
    	 * 邮件:jmzhang_15_cauc@163.com void
    	 * @exception 
    	 * @since  1.0.0
    	 */
    	private Expression factor() {
    		System.out.println("In factor();-----jmzhang-----");
    		if (lookAhead.getType()==TokenType.LPAREN) {
    			matchToken(TokenType.LPAREN, "factor");
    			System.out.println("***********(*********");
    			Expression e=expression();
    			matchToken(TokenType.RPAREN, "factor");
    			System.out.println("***********)*********");
    			ParenthesizedExpression pe=ast.newParenthesizedExpression();
    			pe.setExpression(e);
    			return pe;
    		}else if (lookAhead.getType()==TokenType.IDENTIFIER) {
    			Token id=matchToken(TokenType.IDENTIFIER, "factor");
    			System.out.println("***********id*********");
    			SimpleName sn=ast.newSimpleName(id.getLexeme());
    			return sn;
    		}else if (lookAhead.getType()==TokenType.INTEGER_LITERAL) {
    			Token num=matchToken(TokenType.INTEGER_LITERAL, "factor");
    			System.out.println("***********int*********");
    			NumberLiteral nl=ast.newNumberLiteral(num.getLexeme());
    			return nl;
    		}else {
    			String errorTypes =TokenType.LPAREN.toString()
    					+","+TokenType.IDENTIFIER.toString()
    					+","+TokenType.INTEGER_LITERAL.toString();
    			parsingError(errorTypes, "factor");
    			return null;
    		}
    	}
    }


    测试文件expr3.txt

    {
    	i1=14;
    	i2=i1+2*3;
    	i3=i1-5*(i2%2)+5;
    }

    测试文件expr221.txt

    {
    	i1=14;
    	i2=i1+2*3;
    	i3=i1-5*(i2%2)+5;
    	if(4<5){}
    	if(i1==i4&&i2>=20){
    		i3=i3+1;}
    	else{
    	i3=i3+2;}
    }

    测试文件expr222.txt

    {
    	m=12;n=21;
    	if(m<n){
    		t=m;m=n;n=t;
    	}
    	r=1;
    	d=m%n;
    	while(r!=0){m=n;n=r;r=m%n;}
    	
    }




    更多相关内容
  • 可用于编译原理的课设和平时作业,程序比较简单,结构清晰,程序从文件读入
  • #include #include #include #include using namespace std; #define dd(x) cout #define de(x) cout //词法分析双向链表(存已识别的词单元(endSign)) typedef struct WordAnalysisList ... struct WordAnalysisList *...
  • c++实现的中间代码生成,在语法分析的基础上,对所要分析的文档输出四元式形式。代码能有运行有注释。有使用说明。自己编译原理已通过的作业。
  • 编译原理课程词法分析器,语法分析器(递归实现),中间代码生成
  • 分析中间代码生成程序 含PL0程序,源代码综合性实验报告 分析PL/0编译程序的总体结构、代码生成的方法和过程;具体写出一条语句的中间代码生成过程。
  • 编译原理中间代码生成器实现C++编译原理中间代码生成器实现C++
  • 完整的编译原理实验报告 关于语法、语义和词法分析器三部分的 很全哦 一、实验题目 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 三、实验内容 1. 构造算术表达式的四元式翻译...
  • 实验课上写的编译原理的语义分析和四元式代码生成
  • 编译原理中间代码生成学习课程.pptx
  • 编译原理 中间代码生成PPT课件PPT学习教案.pptx
  • 中间代码生成实验报告.doc
  • 编译原理中间代码生成程序 三元组 报告+程序 第一次上传啊希望能通过 真不能通过啊? 我要受不了了啊。。
  • 华中科技大学 编译原理 面向过程的C语言的编译器设计 功能包括:词法分析和语法分析、语义分析、中间代码生成的 源码 题目:c--语言编译器设计与实现(请为自己的编译器命名) 源语言定义:或采用教材中Decaf语言,...
  • 编译原理实验 实现简单的词法分析 中间代码生成四元式
  • 一个简单的编辑器 编译原理课设 对简单的程序进行语义分析并将中间代码生成
  • 用于编译原理课设 或小作业 很有用的主要是三元式四元式 逆波兰式
  • 编译原理--中间代码生成

    千次阅读 2022-04-01 21:59:30
    静态单赋值形式 静态单赋值形式是另一种中间表示形式, 它有利于实现某些类型的代码优化. SSA中的所有赋值都是针对具有不同名字的变量的. SSA使用一种被称为φ函数的表示规则将x的两处定值合并起来: if(flag) x1...

    语法树的变体

    为表达式构建的无环有向图[DAG]指出了表达式中的公共子表达式.
    

    表达式的有向无环图

    一个DAG的叶子结点对应于原子运算分量,内部结点对应于运算符.
    

    请添加图片描述
    请添加图片描述
    请添加图片描述

    构造DAG的值编码方法

    语法树或DAG图中的结点通常存放在一个记录数组中.
    

    请添加图片描述

    假定结点按图6-6所示的方式存放在一个数组中,
    每个结点通过其值编码引用.
    设每个内部结点的泛型为三元组<op, l, r>,
    其中op是标号,l是其左子结点对应的值编码,r是其右子结点对应的值编码.
    对单目运算符,设r = 0.
    
    // 构造DAG的结点的值编码方法
    输入:标号op,结点l和结点r
    输出:数组中具有三元组<op, l, r>形式的结点的值编码
    方法:搜索
    

    三地址代码

    三地址代码中,一条指令的右侧最多有一个运算符.
    三地址代码是一棵语法树或一个DAG的线性表示形式.
    

    请添加图片描述

    地址和指令

    三地址代码基于两个基本概念:地址和指令.
    地址可以具有如下形式之一:
    1.名字
    源程序的名字.
    实现中,源程序名字被替换为指向符号表条目的指针.
    2.常量
    3.编译器生成的临时变量
    
    下面介绍本书其余部分常用的几种三地址指令.
    1.形如x = y op z
    2.形如x = op y
    3.形如x = y
    4.无条件转移goto L
    5.形如if x goto L或if False x goto L.
    分别当x为真或为假时,
    两个指令的下一步将执行带有标号L的指令.
    否则,下一步将照常执行序列中的后一条指令.
    6.形如if x relop y goto L的条件转移指令.
    7.过程调用和返回通过下列指令来实现:
    param x
    进行参数传递
    call p, n
    y = call p, n
    分别进行过程调用和函数调用
    return y
    是返回指令,y表示返回值
    用法示例:
    param x1
    param x2
    ...
    param xn
    call p, n
    它是过程p(x1, x2, ..., xn)的调用的一部分
    8.待下标的复制指令x = y[i]和x[i] = y.
    9.形如x = &y,x = *y的取地址及通过指针赋值指令.
    *x = y,把y的右值赋给由x指向的目标的右值.
    

    请添加图片描述

    语句do i = i + 1; while(a[i] < v);
    

    四元式表示

    一个四元式有四个字段,分别称为op,arg1,arg2,result.
    字段op包含一个运算符的内部编码.
    这个规则的一些特例:
    1.形如x = minus y的单目运算符指令和赋值指令x = y不使用arg2.
    对x = y这样的赋值语句,op是=,而对大部分其他运算符,赋值运算符是隐含表示的.
    2.像param这样的运算既不使用arg2,也不使用result.
    3.条件或非条件转移指令将目标标号放入result字段.
    

    请添加图片描述

    三元式表示

    一个三元式只有三个字段,
    分别称为op, arg1和arg2.
    使用三元式时,将用运算x op y的位置来表示它的结果,而不是用一个显式的临时名字表示.
    带括号的数字表示指向相应三元式结构的指针.
    

    请添加图片描述
    请添加图片描述

    静态单赋值形式

    静态单赋值形式是另一种中间表示形式,
    它有利于实现某些类型的代码优化.
    SSA中的所有赋值都是针对具有不同名字的变量的.
    

    请添加图片描述

    SSA使用一种被称为φ函数的表示规则将x的两处定值合并起来:
    if(flag) x1 = -1; else x2 = 1;
    x3 = φ(x1, x2);
    如果控制流经过这个条件语句的真分支,φ(x1, x2)的值为x1;
    否则,如果控制流经过假分支,φ函数的值为x2.
    

    类型和声明

    1.类型检查
    利用一组逻辑规则来推理一个程序在运行时刻的行为.
    2.翻译时的应用
    根据一个名字的类型,编译器可确定这个名字在运行时刻需要多大的存储空间.
    其他使用地方如,计算一个数组引用指示的地址,插入显式的类型转换,选择正确版本的算术运算符等.
    

    类型表达式

    类型表达式可能是基本类型,
    也可能通过把称为类型构造算子的运算符作用于类型表达式而得到.
    
    基本类型的集合和类型构造算子根据被检查的具体语言而定.
    我们将使用如下的类型表达式的定义:
    1.基本类型是一个类型表达式.
    一个语言的基本类型通常含boolean,char,integer,float,void
    2.类名是一个类型表达式
    3.将类型构造算子array作用于一个数字和一个类型表达式可以得到一个类型表达式
    4.一个记录是包含有名字段的数据结构.
    将record类型构造算子应用于字段名和相应的类型可构造得到一个类型表达式.
    5.使用类型构造算子->可以构造得到函数类型的类型表达式.
    6.如果s和t是类型表达式,则其笛卡尔积sxt也是类型表达式.
    可以用于描述类型的列表或元组.
    7.类型表达式可以包含取值为类型表达式的变量
    

    类型等价

    当用图来表示类型表达式的时候,两种类型之间结构等价当且仅当下面的某个条件为真:
    1.它们是相同的基本类型
    2.它们是将相同的类型构造算子应用于结构等价的类型而构造得到
    3.一个类型是另一个类型表达式的名字
    

    声明

    请添加图片描述

    局部变量名的存储布局

    名字的类型和相对地址信息保存在相应的符号表条目中.
    

    请添加图片描述

    上述还使用了两个变量t和w,变量的用途是将类型和宽度信息从语法分析树中的B结点传递到对应于产生式C->ε的结点.
    

    请添加图片描述

    声明的序列

    请添加图片描述

    请添加图片描述
    请添加图片描述

    记录和类中的字段

    为6-15的文法加上产生式
    T -> record '{' D '}'
    这个记录类型中的字段D由生成的声明序列描述.
    需小心地处理下面两件事:
    1.一个记录中各个字段的名字必须互不相同.
    2.字段的偏移量是相对于该记录的数据区字段而言的.
    
    为方便起见,
    记录类型将使用一个专用的符号表,
    对它们的各个字段的类型和相对地址进行编码.
    记录类型形如record(t),其中record是类型构造算子,t是一个符号表对象,它保存了有关该记录类型的各个字段的信息.
    

    请添加图片描述

    表达式的翻译

    表达式中的运算

    请添加图片描述

    为方便起见,使用记号gen(x '=' y '+' z)来表示三地址指令x = y + z.
    图6-19中的语法制导定义将赋值语句a = b + -c; 翻译成如下的三地址代码序列:
    t1 = minus c
    t2 = b + t1
    a = t2
    

    增量翻译

    请添加图片描述

    数组元素的寻址

    数组引用的翻译

    令非终结符号L生成一个数组名字再加上一个下标表达式的序列:
    L -> L[E] | id[E]
    下图翻译方案为带有数组引用的表达式生成三地址代码.
    包括了涉及非终结符号L的产生式
    

    请添加图片描述

    非终结符号L有三个综合属性:
    1.L.addr指示一个临时变量.
    2.L.array是一个指向数组名字对应的符号表条目的指针.
    在分析了所有的下标表达式之后,该数组的基地址,也就是L.array.base,被用于确定一个数组引用的实际左值.
    3.L.type是L生成的子数组的类型.
    
    L数组引用.
    引用位置地址为:L.array.base + L.addr
    内容为:L.array.base[L.addr]
    

    请添加图片描述

    类型检查

    为进行类型检查,编译器需给源程序的每一个组成部分赋予一个类型表达式.
    编译器要确定这些类型表达式是否满足一组逻辑规则.
    原则上,如目标代码在保存元素值的同时保存了元素类型的信息,
    则任何检查都可动态地进行.
    

    类型检查规则

    类型检查有两种形式:综合和推导.
    类型综合根据子表达式的类型构造出表达式的类型.
    它要求名字先声明再使用.
    
    一个典型的类型综合规则具有如下形式:
    if f的类型为s->t 且 x的类型为s
    then 表达式f(x)的类型为t
    这里,f和x表示表达式,s->t表示从s到t的函数.
    
    类型推导根据一个语言结构的使用方式来确定该结构的类型.
    令null是一个测试列表是否为空的函数.
    根据这个函数的使用null(x),可指出x需是一个列表类型.
    列表x中的元素类型是未知的.
    
    代表类型表达式的变量使得我们可以考虑未知类型.
    可用希腊字母α,β等作为类型表达式中的类型变量.
    一个典型的类型推导规则具有下面的形式:
    if f(x)是一个表达式
    then 对某些α和β,f的类型为α->β且x的类型为α.
    

    类型转换

    检查E->E1 + E2的语义动作使用了两个函数
    1.max(t1, t2).
    2.如需将类型为t的地址a中的内容转换成w类型的值,则函数widen(a, t, w)将生成类型转换的代码.
    

    请添加图片描述

    请添加图片描述

    函数和运算符的重载

    依据符号所在的上下文不同,被重载的符号会有不同的含义.
    如能为一个名字的每次出现确定其唯一的含义,该名字的重载问题就得到了解决.
    以下是针对重载函数的类型综合规则:
    if f可能的类型为s_{i}->t_{i} (1<=i<=n),其中s_{i} != s_{j}[i != j]
    and x的类型为s_{k}(1<=k<=n)
    then 表达式f(x)的类型为t_{k}
    

    类型推导和多态函数

    术语"多态"指的是任何可以在不同的参数类型上运行的代码片段.
    本节,考虑参数多态.
    这种多态通过参数和类型变量来刻画.
    

    请添加图片描述

    对于任何类型α,length 函数将元素类型为α的列表映射为整型.
    length的类型可写作:
    ∀α,list(α)->integer.
    符号∀是全称量词,它所作用的类型变量称为受限的.
    受限变量可被任意地重命名,但需把这个变量的所有出现一起重命名.
    

    请添加图片描述

    置换,实例和合一
    如t是一个类型表达式,且S是一个置换[即一个从类型变量到类型表达式的映射],
    则用S(t)表示将t中的每个类型变量α的所有出现替换为S(α)后得到的结果.
    S(t)被称为t的一个实例.
    
    对于类型表达式t1和t2,如果S(t1) = S(t2),
    则置换S就是一个合一替换.
    如对t1和t2的任何合一替换,比如说S',下面的条件成立:
    对于任意的t,
    S'(t)是S(t)的一个实例,
    则就说S是t1和t2的最一般化的合一替换.
    
    多态函数的类型推导
    输入:一个由一系列函数定义及紧跟其后的待求值表达式组成的程序.
    一个表达式由多个函数应用和名字构成.
    这些名字具有预定义的多态类型.
    输出:推导出的程序中名字的类型.
    方法:
    只考虑一元函数.
    对于带有两个参数的函数f(x1, x2),
    可将其类型表示为s1 * s2 ->t,其中s1和s2分别是x1和x2的类型.
    而t是函数f(x1, x2)的结果类型.
    通过检查s1是否和a的类型匹配,s2是否和b的类型匹配,
    就可以检查表达式f(a, b)的类型.
    检查输入序列中的函数定义和表达式.
    当一个函数在其后的表达式中被使用时,就使用推导得到的该函数的类型.
    1.对一个函数定义fun id1(id2) = E,
    创建一个新的类型变量α和β.
    将函数id1与类型α->β相关联.
    参数id2和类型α相关联.
    推导出E的类型.
    假设对E进行类型推导后,α表示类型s而β表示类型t.
    推导得到的函数id1的类型就是s->t.
    使用∀量词来限制s->t中任何未受约束的类型变量.
    2.对函数应用E1(E2),推导出E1和E2的类型.
    

    请添加图片描述
    因为E1被用作一个函数它的类型一定具有s->s’的形式.
    假定推导得到的E2的类型为t.
    对s和t进行合一处理.
    如果合一失败,表达式返回类型错误.否则推导得到的E1(E2)的类型为s’.
    3.对一个多态函数的每次出现,将它的类型表达式中的受限变量替换为互不相同的新变量,并移除∀量词.替换得到的类型表达式就是这个多态函数的本次出现所对应的推导类型.
    4.对第一次碰到的变量,引入一个新的类型变量来代表它的类型.

    一个合一算法

    合一就是判断能否通过将两个表达式s和t中的变量替换为某些表达式,
    使得s和t相同.
    类型变量用叶子结点表示,类型构造算子用内部结点表示.
    结点被分成若干的等价类.
    如两个结点在同一个等价类中,则它们代表的类型表达式就必须合一.
    因此,同一个等价类中的内部结点必须具有同样的类型构造算子,且它们的对应子结点需等价.
    

    请添加图片描述
    请添加图片描述
    请添加图片描述
    请添加图片描述

    类型图中的一对结点的合一处理
    
    输入:一个表示类型的图,及需要进行合一处理的结点对m和n
    输出:如果结点m和n表示的表达式可以合一,返回布尔值true.反之,返回false.
    方法:
    结点用一个记录实现,
    记录中的字段用于存放一个二元运算符和分别指向其左右子结点的指针.
    字段set用于保存等价结点的集合.
    每个等价类都有一个结点被选作这个类的唯一代表,
    它的set字段包含一个空指针.
    等价类中其他结点的set字段[可能通过该集合中的其他结点间接地]指向该等价类的代表结点.
    初始时刻,
    每个结点n自身组成一个等价类,
    n是它自己的代表结点.
    下图的合一算法在结点上进行如下两种操作
    1.find(n)返回当前包含结点n的等价类的代表结点
    2.union(m, n)将包含结点m和n的等价类合并.
    如m和n所对应的等价类的代表结点中有一个是非变量的结点,
    则union将这个非变量结点作为合并后的等价类的代表结点;
    否则,union把任意一个原代表结点作为新的代表结点.
    如一个等价类对应于一个带有类型构造算子的类型表达式或基本类型,
    就不能用一个变量作为该等价类的代表.
    否则,两个不等价的表达式可能会通过该变量被合一.
    boolean unify(Node m, Node n)
    {
    	s = find(m);
    	t = find(n);
    	if(s = t) return true;
    	else if(结点s和t表示相同的基本类型) return true;
    	else if(s是一个带有子结点s1和s2的op-结点 and t是一个带有子结点t1和t2的op-结点)
    	{
    		union(s, t);
    		return unify(s1, t1) and unify(s2, t2)}
    	else if(s或者t表示一个变量)
    	{
    		union(s, t);
    		return true;	
    	}
    	else
    	{
    		return false;
    	}
    }
    
    集合的union操作的实现很简单,
    只需改变一个等价类的代表结点的set字段,
    使之指向另一个等价类的代表结点即可.
    为了找到一个结点所属的等价类,沿着各个结点的set字段中的指针前进,直到到达代表结点为止[set字段指针为空指针的结点]
    将一个变量置换为一个表达式的实现方法如下:
    把代表该变量的叶子结点加入到代表该表达式的结点所在的等价类中.
    设m或n表示一个变量的叶子结点,
    假设这个结点已经被放入满足下面条件的等价类中,
    即这个等价类中的一个结点代表的表达式或带有一个类型构造算子,或是一个基本类型.
    则,find将会返回一个反映该类型构造算子或基本类型的代表结点,
    使一个变量不会和两个不同的表达式合一.
    

    请添加图片描述

    如算法返回true,我们可按如下方法构造出一个置换S作为合一替换.
    对每个变量α,find(α)给出α的等价类的代表结点n.
    n所表示的表达式为S(α).
    

    控制流

    布尔表达式

    布尔表达式是将由作用于布尔变量或关系表达式的布尔运算符而构成的.
    关系表达式的形式为E1 rel E2.
    其中E1和E2为算术表达式.
    本节中,考虑的是由如下文法生成的布尔表达式
    B->B || B | B && B | !B | (B) | E rel E | true | false
    通过属性rel.op来指明rel究竟表示6种比较运算符<. <=, =, !=, >, >=中的哪一种.
    按惯例,设||,&&是左结合的.
    ||优先级最低,其次&&,再次!
    

    短路代码

    语句
    if(x < 100 || x > 200 && x != y) x = 0;
    可被翻译为
    

    请添加图片描述

    控制流语句

    现在考虑在按下列文法生成的语句的上下文中,如何把布尔表达式翻译为三地址代码.
    S -> if(B) S1
    S -> if(B) S1 else S2
    S -> while(B) S1
    在这些产生式中,非终结符号B表示一个布尔表达式,非终结符号S表示一个语句.
    

    请添加图片描述
    请添加图片描述

    布尔表达式的控制流翻译

    避免生成冗余的goto指令

    布尔值和跳转代码

    回填

    使用回填技术的一趟式目标代码生成

    布尔表达式的回填

    控制转移语句

    break语句,continue和goto语句

    switch语句

    switch语句的翻译

    switch语句的语法制导翻译

    过程的中间代码

    展开全文
  • 编译原理语义分析和中间代码生成实验报告,基于VS2010开发的纯C#的程序,附程序执行截图
  • 编译原理-中间代码生成

    千次阅读 2019-04-17 10:43:52
    如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 1.2 表示形式 逆波兰式(后缀式)、三地址码(三元式、四元式)、...

     

    1.概述

    1.1 定义

        源程序的一种内部表示,不依赖目标机的结构,易于机械生成目标代码的中间表示。如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。

    1.2 表示形式

        逆波兰式(后缀式)、三地址码(三元式、四元式)、抽象语法树、有向无环图。

    1.3 地位

        如下所示:

     

    2.逆波兰式

    2.1 定义

          把运算量(操作数)写在前面,把运算符写在后面,因此又称为后缀表示法

    2.2 案例

          如下所示:

    表达式语句逆波兰式
    a+bab+
    (a+b)*cab+c*
    a+b*cabc*+
    a=b*c+b*dabc*bd*+=

     

    3.三元地址

    3.1 定义

        指每条代码包含一个运算和三个地址,两个地址用于存放运算对象,一个地址用于存放运算结果。其一般形式为

    x=y op z。

    3.2 四元式

    3.2.1 定义

        一个四元式具有四个域的记录结构,表示为:(op,arg1,arg2,result)。op为运算符;result存放运算结果;arg为运算对象,如果为空,则使用空格,留出位置。

    3.2.2 案例

    例:将 a=b*c+b*d用四元式形式
    写成三地址码的赋值语句形式如下:
        1) t1 = b*c
        2) t2 = b*d
        3) t3 =t1+t2
        4) a = t3
    写成四元形式如下:
        1) (*,b,c,t1)
        2) (*,b,d,t2)
        3) (+,t1,t2,t3)
        4) (=,t3, ,a)

    3.3 三元式

    3.3.1 定义

           一个三元式具有三个域的记录结构,表示为:(op,arg1,arg2)。

    3.3.2 案例

    例:将 a=b*c+b*d用三元形式
    (1) (*,b,c)
    (2) (*,b,d)
    (3) (+,(1),(2))
    (4) (=,(3),a)

    3.4 抽象语法树

    3.4.1 定义

         抽象语法树(Abstract Syntax Code,AST)是语法树的一种简化形式,是源程序的抽象语法结构的树状表示,树的每个节点都表示源代码中的一种结构。

    3.5 有向无环图

    3.5.1 定义

       有向无环图(Directed Acyclic Graph,简称DAG)对表达式中的每个子表达式都有一个结点,内部结点表示运算符,它的孩子代表运算分量。DAG中代表公共子表达式的结点只出现一次,具有多个父结点。

     

     

     

     

     

    展开全文
  • 编译原理中间代码生成

    千次阅读 2020-08-22 15:42:19
    (3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰。 中间语言的形式:后缀式,图表示法,三元式 编译过程中不同语言的翻译或处理方法:说明语句的翻译,赋值语句的...

    一,基本概念 

    翻译为中间语言的好处:

    1)便于进行与机器无关的代码优化;

    2)使编译程序改变目标机更容易;易于编译器的移植

    3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰。

    中间语言的形式:后缀式,图表示法,三元式

    编译过程中不同语言的翻译或处理方法:说明语句的翻译,赋值语句的翻译,布尔表达式的翻译,控制语句的翻译

    中间语言的形式:

    逆波兰表示:后缀式

    图表示法:DAG和AST

    三地址代码:四元式,三元式,间接三元式

    二,后缀式

    后缀式:把操作数写在前面,把算符写在后面

    三,图表示法

    图表示法包括DAG(有向无环图)AST(抽象语法树)

    相同点:对于表达式中的每个子表达式,图中都有一个结点。一个内部结点代表一个操作符,它的孩子代表操作数

    不同点:DAG图中代表公共子表达式的结点具有多个父结点,而在一棵抽象语法树中公共子表达式被表示为重复的子树。        

    前序遍历:前缀式;中序遍历:中缀式;后序遍历:后缀式;

    四,三地址码

    三元式

    三地址码是由下面一般形式的语句构成的序列:x:=y op z

    每条语句通常包含三个地址:两个操作数地址和一个操作结果地址

    四元式

    间接三元式

    五,语义分析中各种语句的处理

    说明语句的翻译

    声明语句的处理方式:不生成可执行代码,只涉及符号表的操作

    声明语句的处理:对每个局部名字,在符号表中建立相应的表项,填写有关的信息(类型,嵌套深度,相对地址等)

    相对地址:相对静态数据区基址或活动记录中局部数据区基址的一个偏移值

    赋值语句的翻译

    布尔表达式的翻译

    布尔表达式: 用布尔运算符号andornot作用到布尔变量或关系表达式上而组成。

    控制语句的翻译

     

    展开全文
  • 编译原理 词法分析,语法分析,中间代码生成 源代码 重庆理工大学编译原理实验。
  • (一) 授课科目:编译原理 (二) 授课内容:实验三 代码生成 (三) 授课类型:实 验 二、教学目的要求: 1.目的:通过设计、编制、调试一个具体的算术表达式求值的程序,加深对编译器计算表达式方法的理解,并...
  • 编译原理--中间代码生成

    千次阅读 2020-01-08 15:25:16
    文章目录基础DAG三地址代码问题声明语句的翻译表达式和赋值语句的翻译控制流翻译布尔表达式的翻译switch 语句的翻译过程调用的翻译回填 基础 DAG 语法树是一种图形化的中间表示。但语法树中,公共子表达式每出现一次...
  • 编译原理》实验三:中间代码生成器 lex + yacc 版 文章来源:中间代码生成器-5-编译原理 项目结构 // headfile.h #ifndef CP_H #define CP_H #include <stdio.h> #include <string.h> #include &...
  • 编译原理实验,实现了一个词法分析器生成Token序列。中间代码、四元式生成。含有实验报告。
  • 中间代码生成 来源:龙书(厚),南大课后作业 p232 6.1.1 为下面的表达式构造 DAG ((x+y)-((x+y)*(x-y)))+((x+y)*(x-y)) Answer 知识点 表达式的有向无环图 (Directed Acyclic Graph, DAG) 能够指出表达式中的...
  • 高级语言 翻译成 LLVM虚拟机代码 可以移植到各种平台 课上要求 能够根据给定方案翻译得到结果即可 难点:实现一遍扫描 目标:转换为三地址语句 如: 常用三地址语句 声明语句的翻译过程 有翻译方案如下(三元...
  • 学完编译原理已经一年了,也有半年被因为学其他东西而没空继续深入学习编译原理。现在终于有机会继续学习了。首先回顾下,编译原理考试第一题的答案。就是翻译的步骤。对于编译,第一步是词法分析。也就是分出一个个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 75,373
精华内容 30,149
关键字:

编译原理中间代码生成

友情链接: 10.1.1.74.193.rar