精华内容
下载资源
问答
  • 编译原理中间代码生成器实现C++编译原理中间代码生成器实现C++
  • 编译原理课程词法分析器,语法分析器(递归实现),中间代码生成
  • 完整的编译原理实验报告 关于语法、语义和词法分析器三部分的 很全哦 一、实验题目 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 三、实验内容 1. 构造算术表达式的四元式翻译...
  • 编译原理中间代码生成--java实现

    万次阅读 2018-05-31 08:17:38
    程序要求能自动生成AST抽象语法树。Lab3Main.javapackage sch.cauc.edu.token; import edu.ustc.cs.compile.platform.interfaces.InterRepresent; /** * * * Lab3Main * 创建人:xrzhang * 时间:2018年5月...

    本人博客内编译原理文章的配套资源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;}
    	
    }




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

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

     

    1.概述

    1.1 定义

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

    1.2 表示形式

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

    1.3 地位

        如下所示:

     

    2.逆波兰式

    2.1 定义

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

    2.2 案例

          如下所示:

    表达式语句 逆波兰式
    a+b ab+
    (a+b)*c ab+c*
    a+b*c abc*+
    a=b*c+b*d abc*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中代表公共子表达式的结点只出现一次,具有多个父结点。

     

     

     

     

     

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

    万次阅读 2016-03-28 22:37:22
    编译程序锁使用的中间代码有多种形式。常见的有逆波兰记号,三元式,四元式,和树形表示。四元式是一种普遍采用的中间代码形式,很类似于三地址指令,有时把这类中间表示称为“三地址代码”,这种表示可以看作是一种...

    预备知识

    源语言->中间代码->目标语言
    中间代码(Intermediate Representation或者IR):复杂性介于源程序语言和机器语言的一种表示形式。
    编译程序锁使用的中间代码有多种形式。常见的有逆波兰记号,三元式,四元式,和树形表示。四元式是一种普遍采用的中间代码形式,很类似于三地址指令,有时把这类中间表示称为“三地址代码”,这种表示可以看作是一种虚拟三地址机的通用汇编码,每条”指令“包含操作符和三个地址,两个是为运算对象的,一个是为结果的。
    基本表达式的翻译模式:
    (1)
    Exp:Exp ASSIGNOP Exp
    |Exp AND Exp
    |Exp OR Exp
    |Exp PLUS Exp
    |Exp MINUS Exp
    |Exp STAR Exp
    |Exp DIV Exp
    |ID
    |INTEGER
    |FLOAT
    ;
    分析:
    (1)要给每一个语法树结点增加一个place属性,这个place属性的值根据以下规则计算。
    1)如果EXP->ID,不需要为ID建立临时变量,place的值就等于变量ID的名字;
    2)如果EXP->INTEGER|FLOAT,即推出常数,不需要为常数建立临时变量,place的值就等于常数值。
    3)E->E1=E2,E1->ID

    emit($1);printf("=");emit($3);

    step1:输出ID;
    step2:输出=
    step3:输出E2.place

    4)i+1;E->E1+E2,newtemp,建立一个临时变量,E.place=E1.place+E2.place,

    $$>t=newtemp();//创建临时变量
    emit($$);//输出创建E.place
    printf("=");//输出=
    emit($1);//输出E1.place
    printf("+");//输出+
    emit($3);//输出E2.place

    也就是说,在语法树的叶子结点存在两种place,一种是ID,即变量名,一种是整数或者浮点数,这两种place值都和临时变量无关,不需要建立临时变量的操作。
    place的值对应到四元式中:
    1)常数
    2)源程序中变量名ID
    3)为生成四元式而建立的临时变量名。
    方法一:变量名采用t加上数字的形式,为所有的临时变量名创建一个符号表,记其在符号表中的位置,这个位置是一个在整数v,从0开始,输出时,输出’t’+v,就可以输出t0,t1这种形式,而且有效地避免了变量名的重复。
    方法二:直接将place设置成整数类型,再设置一个标记数组used[],用了一个整数i,就在标记数组中将used[i]=-1,表示ti已经被用过了。这样一来,创建一个临时变量,相当于设置place的值,然后更改used[]数组的值。

    place应该是一个Union,有3种可能值。
    1)int i(对应INTEGER)
    2)char* (对应变量名ID)
    3)float (对应FLOAT)
    4)int t;对应临时变量编号
    为了能识别place的值是4种中哪一种,再为语法树结点增添一个ptag,1为int,2为float,3为char,4为临时变量编号。

    union
    {
    int i;
    char* s;
    float f;
    }place;
    int tag;//标志位
    
    int main()
    {
    place.s="ID";
    tag=1;
    if(tag==1)
    printf("%s",place);
    }
    

    除了EXP->ID,EXP->常数,每一条基本表达式规则要有一个输出四元式的操作,emit。

    代码更改:
    由于用union导致了内存的错乱(具体什么原因,过后还需要研究),因此将union去掉,4种类型都设置为语法树结点的成员,这样一来可能浪费了空间,但是能保证代码的正确性。

    一、【实验目的】

    通过在词法分析,语法分析和语义分析程序的基础上,将C—源代码翻译成中间代码,认识中间代码的表示形式和生成中间代码的原理和技巧,掌握对简单赋值语句的翻译过程,从而达到对编译器的编译原理有更深的理解,提高代码能力和代码修养。

    二、【实验任务】

    在词法分析,语法分析和语义分析程序的基础上,将C—源代码翻译成中间代码,中间代码的表示采用四元式,本实验中只对基本表达式进行翻译,即将以下规则翻译成四元式:表达式赋值语句,两个表达式的逻辑与,逻辑或,加,减,乘,除。

    Exp:Exp ASSIGNOP Exp 
    |Exp AND Exp 
    |Exp OR Exp 
    |Exp PLUS Exp 
    |Exp MINUS Exp 
    |Exp STAR Exp 
    |Exp DIV Exp 
    |ID 
    |INTEGER 
    |FLOAT 
    ;
    

    三、【实验程序】

    1,程序的编译说明

    (1)程序总共包含4个文件gramtree_v1.h gramtree_v1.c gramtree.l gramtree_v1.y
    gramtree_v1.h gramtree_v1.c定义和实现了:
    1)语法树结构体,语法树创建函数,语法树遍历函数
    2)变量符号表结构体,变量符号表的建立函数,查找变量是否已定义的函数,查找变量类型的函数
    3)函数符号表结构体,函数符号表的建立函数,查找函数是否已定义,查找函数类型,查找函数形参个数。
    4)数组符号表,数组符号表的建立函数,查找数组是否已定义的函数,查找数组类型的函数
    5)结构体符号表,结构体符号表的建立函数,查找结构体是否已定义的函数
    6)关于生成中间表达式的2个函数:newtemp()和emit()。newtemp生成了一个临时变量,emit将一个语法结点的place属性输出到屏幕。
    (2)gramtree.l是flex词法分析模块
    (3)gramtree_v1.y是bison语法分析模块。
    在bison文件中,在对应的变量定义,函数定义,数组定义 ,结构体定义,变量调用,函数调用,数组调用,结构体调用对应的语法规则中,建立或者查询对应的符号表,实现语义分析和特定错误的检测 然后输出错误类型和错误行号。
    (4)编译时使用Makefile文件:
    1)编写Makefile文件内容,执行:vim Makefile

    2,实验分析

    (1)要给每一个语法树结点增加一个place属性,这个place属性的值根据以下规则计算。
    1)如果EXP->ID,不需要为ID建立临时变量,place的值就等于变量ID的名字;
    2)如果EXP->INTEGER|FLOAT,即推出常数,不需要为常数建立临时变量,place的值就等于常数值。
    3)对于规则E->E1=E2,(E1->ID), E->E1&&E2,E->E1||E2,E->E1+E2,E->E1-E2,E->E1*E2,E->E1/E2:
    step1:生成一个临时变量.
    临时变量的名字符合t加上一个数字的表示形式,E.place的值就等于生成的临时变量;
    step2:输出E.place->输出E1.place->输出操作符->输出E2.place。
    这样就完成了一条四元式的生成和输出。

    (2)属性place的设置
    在语法树的叶子结点存在两种place,一种是ID,即变量名;另一种是整数或者浮点数,这两种place值都和临时变量无关,不需要建立临时变量的操作。
    place的值对应到四元式中,有以下3种情况:
    1)常数
    2)源程序中变量名ID
    3)为生成四元式而建立的临时变量名。

    生成临时变量的方法
    直接将place设置成整数类型,再设置一个标记数组used[],用了一个整数i,就在标记数组中将used[i]=-1,表示ti已经被用过了。这样一来,创建一个临时变量,相当于设置place的值,然后更改used[]数组的值。
    于是place的数据类型有以下3种可能值。
    1)int i(对应INTEGER)
    2)char* (对应变量名ID)
    3)float (对应FLOAT)
    4)int t;对应临时变量编号
    为了能识别place的值是4种中哪一种,再为语法树结点增添一个ptag,1为int,2为float,3为char,4为临时变量编号。

    3,实验代码

    (1)在语法树结点中增加以下5个成员:place的4种数据类型,和一个用以标志类型的整型变量ptag。

    struct ast
    {
    /*用于生成中间代码的变量,place的4种类型,*/
        int i;//Integer
        float f;//FLOAT
        char id[30];//变量名ID
        int t;//临时变量t编号
    
        int ptag;//用以标志place的类型1,2,3,4
    }
    

    (2)生成临时变量的函数newtemp()和输出E.place的函数emit()

    /*关于中间代码的实现函数:创建临时变量&输出四元式*/
    int newtemp()//创建临时变量
    {
        int i=0;
        for(i=0; i<100; ++i)//在used[]中找到一个没有被用过的编号
        {
            if(used[i]==0)
            {
                used[i]=i+1;
                return i;//返回的编号就是t的编号
            }
        }
    }
    
    void emit(struct ast* tp)//输出四元式
    {
        if(tp->ptag==1)//place的值是INTEGER
            printf("%d",tp->i);
        else if(tp->ptag==2)
            printf("%2f",tp->f);//place的值是FLOAT
        else if(tp->ptag==3)
            printf("%s",tp->id);//place的值是ID变量名字
        else//place的值是临时变量编号
            printf("t%d",tp->t);
    }
    

    (3)在基本表达式的语义规则中增加:

    /*Expressions*/
    Exp:Exp ASSIGNOP Exp        /*E1->ID,不需要建立临时变量*/
    {
    emit($1);//输出E1.place
        printf("=");//输出‘=’
        emit($3);//输出E2.place
        printf("\n");
        }
    
    |Exp AND Exp        /*逻辑与运算:需要建立临时变量*/
        {
        $$->t=newtemp();//E.place等于新创建的临时变量
    	emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("&&");//输出‘&&’
        emit($3);//输出E2.place 
        printf("\n");
        }
    
    |Exp OR Exp /*逻辑或运算:需要建立临时变量*/
        {
        $$->t=newtemp();//E.place等于新创建的临时变量
    	emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("||");//输出‘||’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp PLUS Exp       /*加法运算:需要建立临时变量*/
        {
        $$->t=newtemp();//E.place等于新创建的临时变量
    emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("+");//输出‘+’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp MINUS Exp  /*减法运算:需要建立临时变量*/
        {
        $$->t=newtemp();//E.place等于新创建的临时变量
    emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("-");//输出‘-’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp STAR Exp       /*乘法运算:需要建立临时变量*/
        {
        $$->t=newtemp();//E.place等于新创建的临时变量
    emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("*");//输出‘*’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp DIV Exp    /*除法运算:需要建立临时变量*/
        {
            $$->t=newtemp();//E.place等于新创建的临时变量
    	emit($$);//输出E.place
            printf("=");//输出‘=’
            emit($1);//输出E1.place
            printf("/");//输出‘/’
            emit($3);//输出E2.place
            printf("\n");
            }
    
        |ID  /*E->ID,不需要建立临时变量*/
        {
        strcpy($$->id,$1->content);//E.place=ID的名字
    	$$->ptag=3;//记录E.place的类型为3
        }
    
        |INTEGER     /*E->INTEGER,不需要建立临时变量*/
        {
        $$->i=$1->value;//E.place=value
    	$$->ptag=1;//记录E.place的类型为1
        }
    
        |FLOAT      /*E->FLOAT,不需要建立临时变量*/
        {
        $$->f=$1->value;//E.place=value
    	$$->ptag=2;//记录E.place的类型为2
        }
    
    
    /*
    *Name:gramtree_v1.y
    *Author:WangLin
    *Created on:2015-10-03
    *Version3.0
    *Function:bison语法分析&语义分析&基本表达式的中间代码生成(四元式)
    */
    %{
    #include<unistd.h>
    #include<stdio.h>
    # include<string.h> 
    #include "gramtree_v1.h"
    %}
    
    %union{
    struct ast* a;
    double d;
    }
    /*declare tokens*/
    %token  <a> INTEGER FLOAT
    %token <a> TYPE STRUCT RETURN IF ELSE WHILE ID SPACE SEMI COMMA ASSIGNOP RELOP PLUS
    MINUS STAR DIV AND OR DOT NOT LP RP LB RB LC RC AERROR
    %token <a> EOL
    %type  <a> Program ExtDefList ExtDef ExtDecList Specifire StructSpecifire 
    OptTag  Tag VarDec  FunDec VarList ParamDec Compst StmtList Stmt DefList Def DecList Dec Exp Args
    
    /*priority*/
    %right ASSIGNOP
    %left OR
    %left AND
    %left RELOP
    %left PLUS MINUS
    %left STAR DIV
    %right NOT 
    %left LP RP LB RB DOT
    %%
    Program:ExtDefList {$$=newast("Program",1,$1);}
    	;
    ExtDefList:ExtDef ExtDefList {$$=newast("ExtDefList",2,$1,$2);}
    	| {$$=newast("ExtDefList",0,-1);}
    	;
    ExtDef:Specifire ExtDecList SEMI    
    	{
    	$$=newast("ExtDef",3,$1,$2,$3);
    	if(exitvar($2))
    	printf("Error type 3 at Line %d:Redefined Variable '%s'\n",yylineno,$2->content);
    	else newvar(2,$1,$2);
    	}    
    	|Specifire SEMI	{$$=newast("ExtDef",2,$1,$2);}
    	|Specifire FunDec Compst
    	{
    	$$=newast("ExtDef",3,$1,$2,$3);
    	 newfunc(4,$1);
    	}
    	;
    ExtDecList:VarDec {$$=newast("ExtDecList",1,$1);}
    	|VarDec COMMA ExtDecList {$$=newast("ExtDecList",3,$1,$2,$3);}
    	;
    /*Specifire*/
    Specifire:TYPE {$$=newast("Specifire",1,$1);}
    	|StructSpecifire {$$=newast("Specifire",1,$1);}
    	;
    StructSpecifire:STRUCT OptTag LC DefList RC 
    	{
    	$$=newast("StructSpecifire",5,$1,$2,$3,$4,$5);
    	if(exitstruc($2))
    		printf("Error type 16 at Line %d:Duplicated name '%s'\n",yylineno,$2->content);
    	else newstruc(1,$2);
    	}
    	|STRUCT Tag {
    	$$=newast("StructSpecifire",2,$1,$2);
    	if(!exitstruc($2))
    	printf("Error type 17 at Line %d:undefined structure '%s'\n",yylineno,$2->content);
    	}
    	;
    OptTag:ID {$$=newast("OptTag",1,$1);}
    	|{$$=newast("OptTag",0,-1);}
    	;
    Tag:ID {$$=newast("Tag",1,$1);}
    	;
    /*Declarators*/
    VarDec:ID {$$=newast("VarDec",1,$1);$$->tag=1;}
    	| VarDec LB INTEGER RB {$$=newast("VarDec",4,$1,$2,$3,$4);$$->content=$1->content;$$->tag=4;}
    	;
    FunDec:ID LP VarList RP 
    	{$$=newast("FunDec",4,$1,$2,$3,$4);$$->content=$1->content;
    	if(exitfunc($1))printf("Error type 4 at Line %d:Redefined Function '%s'\n",yylineno,$1->content);
    	else newfunc(2,$1);}
    	|ID LP RP
    	 {$$=newast("FunDec",3,$1,$2,$3);$$->content=$1->content;
    	if(exitfunc($1))printf("Error type 4 at Line %d:Redefined Function '%s'\n",yylineno,$1->content);
            else newfunc(2,$1);}
    	;
    VarList:ParamDec COMMA VarList {$$=newast("VarList",3,$1,$2,$3);}
    	|ParamDec {$$=newast("VarList",1,$1);}
    	;
    ParamDec:Specifire VarDec {$$=newast("ParamDec",2,$1,$2);newvar(2,$1,$2);newfunc(1);}
        ;
    
    /*Statement*/
    Compst:LC DefList StmtList RC {$$=newast("Compst",4,$1,$2,$3,$4);}
    	;
    StmtList:Stmt StmtList{$$=newast("StmtList",2,$1,$2);}
    	| {$$=newast("StmtList",0,-1);}
    	;
    Stmt:Exp SEMI {$$=newast("Stmt",2,$1,$2);}
    	|Compst {$$=newast("Stmt",1,$1);}
    	|RETURN Exp SEMI {$$=newast("Stmt",3,$1,$2,$3);
    		newfunc(3,$2);}
    	|IF LP Exp RP Stmt {$$=newast("Stmt",5,$1,$2,$3,$4,$5);}
    	|IF LP Exp RP Stmt ELSE Stmt {$$=newast("Stmt",7,$1,$2,$3,$4,$5,$6,$7);}
    	|WHILE LP Exp RP Stmt {$$=newast("Stmt",5,$1,$2,$3,$4,$5);}
    	;
    /*Local Definitions*/
    DefList:Def DefList{$$=newast("DefList",2,$1,$2);}
    	| {$$=newast("DefList",0,-1);}
    	;
    Def:Specifire DecList SEMI {$$=newast("Def",3,$1,$2,$3);
    	if(exitvar($2)||exitarray($2))  printf("Error type 3 at Line %d:Redefined Variable '%s'\n",yylineno,$2->content);
            else if($2->tag==4) newarray(2,$1,$2);
    	else newvar(2,$1,$2);}
    	;
    DecList:Dec {$$=newast("DecList",1,$1);}
    	|Dec COMMA DecList {$$=newast("DecList",3,$1,$2,$3);$$->tag=$3->tag;}
    	;
    Dec:VarDec {$$=newast("Dec",1,$1);}
    	|VarDec ASSIGNOP Exp {$$=newast("Dec",3,$1,$2,$3);$$->content=$1->content;}
    	;
    /*Expressions*/
    Exp:Exp ASSIGNOP Exp/*E1->ID,不需要建立临时变量*/
    	{$$=newast("Exp",3,$1,$2,$3);
        if($1->type!=NULL&&$3->type!=NULL&&strcmp($1->type,$3->type)){printf("Error type 5 at Line %d:Type mismatched for assignment.\n ",yylineno);}
        if($1->tag==3)printf("Error type 6 at Line %d:the left-hand side of an  assignment must be a variable.\n ",yylineno);
        emit($1);//输出E1.place
        printf("=");//输出‘=’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp AND Exp /*与运算:需要建立临时变量*/
        {$$=newast("Exp",3,$1,$2,$3);
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("&&");//输出‘&&’
        emit($3);//输出E2.place 
        printf("\n");
        }
    
        |Exp OR Exp/*或运算:需要建立临时变量*/
        {$$=newast("Exp",3,$1,$2,$3);
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("||");//输出‘||’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp RELOP Exp{$$=newast("Exp",3,$1,$2,$3);}
    
        |Exp PLUS Exp/*加法运算:需要建立临时变量*/
        {$$=newast("Exp",3,$1,$2,$3); 
    	if($1->type!=NULL&&$3->type!=NULL&&strcmp($1->type,$3->type)){printf("Error type 7 at Line %d:Type mismatched for operand.\n ",yylineno);}
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("+");//输出‘+’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp MINUS Exp/*减法运算:需要建立临时变量*/
        {$$=newast("Exp",3,$1,$2,$3);
    	if($1->type!=NULL&&$3->type!=NULL&&strcmp($1->type,$3->type)){printf("Error type 7 at Line %d:Type mismatched for operand.\n ",yylineno);}
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("-");//输出‘-’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp STAR Exp/*乘法运算:需要建立临时变量*/
         {$$=newast("Exp",3,$1,$2,$3);
    	if($1->type!=NULL&&$3->type!=NULL&&strcmp($1->type,$3->type)){printf("Error type 7 at Line %d:Type mismatched for operand.\n ",yylineno);}
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("*");//输出‘*’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |Exp DIV Exp/*除法运算:需要建立临时变量*/
         {$$=newast("Exp",3,$1,$2,$3);
    	if($1->type!=NULL&&$3->type!=NULL&&strcmp($1->type,$3->type)){printf("Error type 7 at Line %d:Type mismatched for operand.\n ",yylineno);}
    	$$->t=newtemp();//E.place等于新创建的临时变量
        emit($$);//输出E.place
        printf("=");//输出‘=’
        emit($1);//输出E1.place
        printf("/");//输出‘/’
        emit($3);//输出E2.place
        printf("\n");
        }
    
        |LP Exp RP{$$=newast("Exp",3,$1,$2,$3);}
    	|MINUS Exp {$$=newast("Exp",2,$1,$2);}
        |NOT Exp {$$=newast("Exp",2,$1,$2);}
        |ID LP Args RP {$$=newast("Exp",4,$1,$2,$3,$4);
    	if((!exitfunc($1))&&(exitvar($1)||exitarray($1)))printf("Error type 11 at Line %d:'%s'is not a function.\n ",yylineno,$1->content);
    	else if(!exitfunc($1)){printf("Error type 2 at Line %d:undefined Function %s\n ",yylineno,$1->content);}
    	else if(pnumfunc($1)!=rpnum)printf("Error type 9 at Line %d:parameters num mismatched for function: %s\n ",yylineno,$1->content);}
        |ID LP RP {$$=newast("Exp",3,$1,$2,$3);}
        |Exp LB Exp RB 
    	{$$=newast("Exp",4,$1,$2,$3,$4);
    	if(strcmp($3->type,"int"))printf("Error type 12 at Line %d:%.1f is not a integer.\n",yylineno,$3->value);
    	if((!exitarray($1))&&(exitvar($1)||exitfunc($1)))printf("Error type 10 at Line %d:'%s'is not an array.\n ",yylineno,$1->content);
        else if(!exitarray($1)){printf("Error type 2 at Line %d:undefined Array %s\n ",yylineno,$1->content);}}
        |Exp DOT ID 
    	{$$=newast("Exp",3,$1,$2,$3);if(!exitstruc($1))printf("Error type 13 at Line %d:Illegal use of '.'.\n",yylineno);}
    
        |ID /*E->ID,不需要建立临时变量*/
        {$$=newast("Exp",1,$1);
    	if(!exitvar($1)&&!exitarray($1))
    	{printf("Error type 1 at Line %d:undefined variable %s\n ",yylineno,$1->content);}
    	else $$->type=typevar($1);
        strcpy($$->id,$1->content);//E.place=ID的名字
    	$$->ptag=3;//记录E.place的类型为3
        }
    
        |INTEGER /*E->INTEGER,不需要建立临时变量*/
        {$$=newast("Exp",1,$1);$$->tag=3;$$->type="int";
    	$$->i=$1->value;//E.place=value
        $$->ptag=1;//记录E.place的类型为1
        }
    
        |FLOAT/*E->FLOAT,不需要建立临时变量*/
        {$$=newast("Exp",1,$1);$$->tag=3;$$->type="float";$$->value=$1->value;
        $$->f=$1->value;//E.place=value
    	$$->ptag=2;//记录E.place的类型为2
        }
        ;
    
    Args:Exp COMMA Args {$$=newast("Args",3,$1,$2,$3);rpnum+=1;}
        |Exp {$$=newast("Args",1,$1);rpnum+=1;}
        ;
    %%
    
    

    四、 【实验结果】

    1.输入内容: test1.c的内容如下:

    [root@localhost IR]# cat test1.c
    int main()
    {
    float x;
    float y;
    float z;
    x=1.5;
    y=1.6;
    z=x+y;
    z=x-y;
    z=x*y;
    z=x/y;
    z=x&&y;
    z=x||y;
    
    z=x+y-1.0-2.0/y;
    z=x*2.5+x*y-x/2.0;
    
    z=x||y+x&&y;
    }
    

    2.输出内容:注释和空行都是为了直观加上的,不是输出的一部分。

    [root@localhost IR]# cat test1.c|./a.out 
    x=1.500000      /*对应x=1.5;*/    
    y=1.600000      /*对应y=1.6;*/    
    
    t0=x+y          /*对应z=x+y;*/    
    z=t0
    
    t1=x-y          /*对应z=x-y;*/    
    z=t1
    
    t2=x*y          /*对应z=x*y;*/    
    z=t2
    
    t3=x/y          /*对应z=x/y;*/        
    z=t3
    
    t4=x&&y     /*对应z=x&&y;*/   
    z=t4
    
    t5=x||y         /*对应z=x||y;*/   
    z=t5
    
    t6=x+y          /*对应z=x+y-1.0-2.0/y;*/  
    t7=t6-1.000000
    t8=2.000000/y
    t9=t7-t8
    z=t9
    
    t10=x*2.500000      /*对应z=x*2.5+x*y-x/2.0;*/    
    t11=x*y
    t12=t10+t11
    t13=x/2.000000
    t14=t12-t13
    z=t14
    
    t15=y+x             /*对应z=x||y+x&&y;*/  
    t16=t15&&y
    t17=x||t16
    z=t17
    
    

    3.实验结果分析:
    1)从输出结果可以看出,程序正确处理了E->ID,E->常数,E->E1操作符E2的各种情况;E->ID时,输出的E.place就是ID的名字,E->常数时输出的E.place就是常数的值,如表达式x=1.5和y=1.6。E->E1操作符E2时,E.place是临时变量名。

    2)正确处理表达式中的优先级。
    如 z=x*2.5+x*y-x/2.0;由于乘法和除法的优先级高于加法和减法,因此先对乘法和除法进行计算,最后算加和减。对于表达式z=x||y+x&&y;由于加减的优先级高于逻辑与和逻辑或,因此程序先计算加和减,再计算逻辑与和逻辑或。

    3)正确处理了临时变量的编号。

    五、【实验总结】

    1.place的设置—Union的舍弃
    由于place的数据类型可能有4种,但这4种并不是同时出现的,一次只是一种类型,这和Union(共同体)的思想恰好一致,因此一开始想把place应该是一个Union。
    union
    {
    int i;//Integer
    float f;//FLOAT
    char id[30];//变量名ID
    int t;//临时变量t编号
    }place;
    但在实践的过程中,union导致了内存的错乱(具体什么原因,过后还需要研究),因此只能将union舍弃掉,4种类型都直接设置为语法树结点的成员,这样一来可能浪费了空间,但是能保证代码的正确性。

    2.临时变量编号数组used[]的使用
    used[]的使用是一个比较巧妙的设计,既不占用空间,操作也很简单,但是这只是针对于本次实验只对基本表达式进行翻译的设计,如果提升实验难度,要求对语句等进行翻译,这种设计多半是行不通的,需要再寻求一种更强大更健壮的设计。

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

    千次阅读 2020-04-07 12:35:44
    如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 为什么不直接翻译成机器码呢,而多此一举生成中间代码再转换?(代码的...

    中间代码定义

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

    为什么不直接翻译成机器码呢,而多此一举生成中间代码再转换?(代码的鲁棒性)

    是为了提高编译器的可移植性,因为不同的cpu的指令集是不一样的,假如直接翻译成机器代码,那么当你换了一块cpu之后,可能你的编译器就完全不能运行了,所以为了鲁棒性,将代码先翻译成中间代码,然后在能在多个不同的cpu上做出相应的改变并且运行了。
    在这里插入图片描述

    使用中间代码的好处:

    1)一是便于编译器程序的开发和移植(鲁棒性)
    2)二是代码进行优化处理

    常见的中间代码表示形式

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

    逆波兰式 运算量(操作数)写在前面,把运算符写在后面,因此又称为后缀表示法
    在这里插入图片描述

    三地址码——最常用的中间代码形式是三地址码,它的实现形式常采用四元式形式。
    指每条代码包含一个运算和三个地址,两个地址用于存放运算对象,一个地址用于存放运算结果。其一般形式为x=y op z。
    四元式
    一个四元式具有四个域的记录结构,表示为:(op,arg1,arg2,result)。op为运算符;result存放运算结果;arg为运算对象,如果为空,则使用空格,留出位置。
    四元式与三元式的唯一区别:
    将由序号所表示的运算结果改为:用(临时)变量来表示。
    此改变使得四元式的运算结果与其在四元式序列中的位置无关.为代码的优化提供了极大方便,因为这样可以删除或移动四元式而不会影响运算结果.
    在这里插入图片描述

    例:将 a=b*c+b*d用三元形式
    (1) (*,b,c)
    (2) (*,b,d)
    (3) (+,(1),(2))
    (4) (=,(3),a)
    
    例:将 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)
    

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

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

    一个例子

    声明语句的翻译之变量的声明 一个变量的声明应该由两部分来完成:类型的定义和变量的声明
    类型定义:为编译器提供存储空间大小的信息
    变量声明:为变量分配存储空间
    组合数据的类型定义和变量声明:定义与声明在一起,定义与声明分离.

    引用于介篇文章

    展开全文
  • 采用递归下降语法制导翻译法,对算术表达式、赋值语句进行语义分析并生成三地址指令。
  • 编译原理代码生成

    千次阅读 2017-12-18 16:13:41
    目标代码生成阶段的任务是:将此前的中间代码转换成特定机器上的机器语言或汇编语言,这种转换程序便被称为代码生成器。1. 程序移植性和编译器模块设计的关系 之所以将编译原理分成这种多阶段多模块的组织形式,...
  • (3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰。 中间语言的形式:后缀式,图表示法,三元式 编译过程中不同语言的翻译或处理方法:说明语句的翻译,赋值语句的...
  • 一个简单的编辑器 编译原理课设 对简单的程序进行语义分析并将中间代码生成
  • 编译原理实验:语义分析及中间代码生成

    万次阅读 多人点赞 2018-09-29 22:47:27
    编译原理实验报告:语义分析及中间代码生成1. 实验题目:语义分析及中间代码生成实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目:语义分析及中间代码生成 实验目的 通过...
  • 编译原理实验 语义分析与中间代码生成 Sample语言的语义和代码生成规则,熟悉Sample语言的语义分析和代码生成过
  • 表达式翻译器-1-编译原理   词法分析器-2-编译原理 递归下降法的语法分析器-3-编译原理 递归下降法的语法分析器-3.1-编译原理 用Yacc实现语法分析器-4-编译原理 ...中间代码生成器-5-编译原理      ...
  • 编译原理 词法分析,语法分析,中间代码生成 源代码 重庆理工大学编译原理实验。
  • 实验课上写的编译原理的语义分析和四元式代码生成
  • 编译原理(七)中间代码生成

    千次阅读 2018-01-27 20:03:09
    我们以一个排序来演示中间代码生成 语义动作用到的函数 mkTable(previous):创建符号表,参数为过程id enter(table,name,type,offset):进入符号表,四个参数分别为:表名,参数名称,参数类型,下标 addWidth...
  • Java 实现《编译原理中间代码生成 -逆波兰式生成与计算 编译原理学习笔记 (一)逆波兰式是什么? 逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫 后缀表达式(将运算符写在操作数之后) 一般的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,559
精华内容 26,623
关键字:

编译原理中间代码生成