Semantic Analysis - Revision history

Root: Redirected page to ist:Semantic Analysis

2018-12-06T18:08:34Z

Redirected page to ist:Semantic Analysis

← Older revision		Revision as of 18:08, 6 December 2018
Line 1:		Line 1:
	~~{{NAVCompiladores}}~~		#REDIRECT [[ist:Semantic Analysis]]
	~~{{TOCright}}~~
	* Abstract syntax tree; nodes
	* Declarations and types

	~~== Representing Types ==~~

	* Symbols and types
	* Symbol table
	* Types in variable and function declarations

	~~Any program in any language must manipulate objects to perform its various tasks. These objects are characterized by their structure, which is mapped to the programmer level as data types.~~

	~~Data types may be explicit, as in the C/C++ family of languages, or they may be inferred from the primitive objects and the operations they are subject to (e.g. CAML).~~

	~~== The Symbol Table ==~~

	~~A interface pública da tabela de símbolos é a seguinte (foram omitidas todas as partes não públicas, assim como os métodos de construção/destruição):~~

	~~<cpp>~~
	~~namespace cdk {~~

	~~template<typename Symbol>~~
	~~class symbol_table {~~
	~~public:~~
	~~void push();~~

	~~void pop();~~

	~~bool insert(const std::string &name, std::shared_ptr<Symbol> symbol);~~

	~~bool replace_local(const std::string &name, std::shared_ptr<Symbol> symbol);~~

	~~bool replace(const std::string &name, std::shared_ptr<Symbol> symbol);~~

	~~std::shared_ptr<Symbol> find_local(const std::string &name);~~

	~~std::shared_ptr<Symbol> find(const std::string &name, size_t from = 0) const;~~

	};
	~~</cpp>~~

	* '''push''' - create a new context and make it current.
	* '''pop''' - destroy the current context: the previous context becomes the current one. If the first context is reached no operation is performed.
	* '''insert''' - define a new identifier in the local (current) context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if this is a new identifier (may shadow another defined in an upper context). Returns false if the identifier already exists in the current context.
	* '''replace_local''' - replace the data corresponding to a symbol in the current context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.
	* '''replace''' - replace the data corresponding to a symbol (look for the symbol in all available contexts, starting with the innermost one): ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.
	* '''find_local''' - search for a symbol in the local (current) context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns the symbol if it exists; and nullptr if the symbol does not exist in the current context.
	* '''find''' - search for a symbol in the avaible contexts, starting with the first one and proceeding until reaching the outermost context. ''name'' is the symbol's name; from how many contexts up from the current one (zero). Returns nullptr if the symbol cannot be found in any of the contexts; or, the symbol and corresponding attributes.

	~~== Type Checking: Using Visitors ==~~

	~~Type checking is the process of verifying whether the types used in the various language constructs are appropriate. It can be performed at compile time (static type checking) or at run time.~~

	~~The type checking discussed here is the static approach, i.e., checking whether the types used for objects and the operations that manipulate them at compile time are consistent.~~

	In the approach followed by CDK-based compilers, code generation is carried out by visitors that are responsible for traversing the abstract syntax tree and generate, evaluating each node. Node evaluation may depend on the specificities of the data types being manipulated, the simplest of which is the data type's size, important in all memory-related operations.

	~~== Examples ==~~
	~~=== Type checking example: the Tiny language ===~~

	The following example considers a simple grammar and performs the whole of the semantic analysis process and, finally, generates the corresponding C code. The semantic analysis process must account for variables (they must be declared before they can be used) and for their types (all types must be used correctly).

	* [[~~Semantic Analysis/The Tiny language~~: ~~semantic analysis example and C generation\|The Tiny language: semantic analysis example and C generation]]~~

	~~=== Type checking example: the Simple language ===~~

	The following example considers an evolution of Compact, called Simple. Where Compact forces some verification via syntactic analysis (thus, presenting low flexibility), Simple has a richer grammar and, consequently, admits constructions that may not be correct in what concerns types of operators, functions, and their arguments. Type checking in this case is built-in, since, without it, it would be impossible to guarantee the correctness of any expression.

	* [[Semantic Analysis~~/The Simple language: semantic analysis\|The Simple language: semantic analysis]]~~
	~~<!--~~
	~~=== Type checking example: the Compact language [obsolete]===~~

	~~The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.~~

	* [[Semantic Analysis/The Compact language: semantic analysis example and C generation\|The Compact language: semantic analysis example and C generation]]
	~~-->~~

	~~== Exercises ==~~

	* [[Semantic Analysis/Exercise 01\|Exercise 01]] - The "Let" language

	~~[[category:Compiladores]]~~
	~~[[category:Ensino~~]]

Root: /* The Symbol Table */

2018-05-03T15:37:00Z

The Symbol Table

← Older revision		Revision as of 15:37, 3 May 2018
Line 46:		Line 46:
	* '''replace_local''' - replace the data corresponding to a symbol in the current context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.		* '''replace_local''' - replace the data corresponding to a symbol in the current context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.
	* '''replace''' - replace the data corresponding to a symbol (look for the symbol in all available contexts, starting with the innermost one): ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.		* '''replace''' - replace the data corresponding to a symbol (look for the symbol in all available contexts, starting with the innermost one): ''name'' is the symbol's name; ''symbol'' is the symbol. Returns true if the symbol exists; false if the symbol does not exist in any of the contexts.
	* '''find_local''' - search for a symbol in the local (current) context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns ~~true if~~ the symbol exists; ~~false~~ if the symbol does not exist in the current context.		* '''find_local''' - search for a symbol in the local (current) context: ''name'' is the symbol's name; ''symbol'' is the symbol. Returns the symbol if it exists; and nullptr if the symbol does not exist in the current context.
	* '''find''' - search for a symbol in the avaible contexts, starting with the first one and proceeding until reaching the outermost context. ''name'' is the symbol's name; from how many contexts up from the current one (zero). Returns nullptr if the symbol cannot be found in any of the contexts; or, the symbol and corresponding attributes.		* '''find''' - search for a symbol in the avaible contexts, starting with the first one and proceeding until reaching the outermost context. ''name'' is the symbol's name; from how many contexts up from the current one (zero). Returns nullptr if the symbol cannot be found in any of the contexts; or, the symbol and corresponding attributes.

Root: /* Examples */

2017-01-04T14:46:26Z

Examples

← Older revision		Revision as of 14:46, 4 January 2017
Line 69:		Line 69:

	* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]		* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]
			<!--
	<!--=== Type checking example: the Compact language [obsolete]===		=== Type checking example: the Compact language [obsolete]===

	The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.		The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.

Root: /* Type checking example: the Compact language [obsolete] */

2017-01-04T14:46:08Z

Type checking example: the Compact language [obsolete]

← Older revision		Revision as of 14:46, 4 January 2017
Line 70:		Line 70:
	* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]		* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]

	=== Type checking example: the Compact language [obsolete]===		<!--=== Type checking example: the Compact language [obsolete]===

	The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.		The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.

	* [[Semantic Analysis/The Compact language: semantic analysis example and C generation\|The Compact language: semantic analysis example and C generation]]		* [[Semantic Analysis/The Compact language: semantic analysis example and C generation\|The Compact language: semantic analysis example and C generation]]
			-->

	== Exercises ==		== Exercises ==

Root at 18:16, 29 April 2015

2015-04-29T18:16:55Z

← Older revision		Revision as of 18:16, 29 April 2015
Line 51:		Line 51:
	== Type Checking: Using Visitors ==		== Type Checking: Using Visitors ==

	Type checking is the process of verifying whether the types used in the various language constructs are appropriate. It can be performed at compile ~~type~~ (static type checking) or at run time.		Type checking is the process of verifying whether the types used in the various language constructs are appropriate. It can be performed at compile time (static type checking) or at run time.

	The type checking discussed here is the static approach, i.e., checking whether the types used for objects and the operations that manipulate them at compile time are consistent.		The type checking discussed here is the static approach, i.e., checking whether the types used for objects and the operations that manipulate them at compile time are consistent.

Root: /* The Symbol Table */

2015-04-13T23:46:35Z

The Symbol Table

← Older revision		Revision as of 23:46, 13 April 2015
Line 25:		Line 25:
	public:		public:
	void push();		void push();

	void pop();		void pop();

	bool insert(const std::string &name, std::shared_ptr<Symbol> symbol);		bool insert(const std::string &name, std::shared_ptr<Symbol> symbol);

	bool replace_local(const std::string &name, std::shared_ptr<Symbol> symbol);		bool replace_local(const std::string &name, std::shared_ptr<Symbol> symbol);

	bool replace(const std::string &name, std::shared_ptr<Symbol> symbol);		bool replace(const std::string &name, std::shared_ptr<Symbol> symbol);

	std::shared_ptr<Symbol> find_local(const std::string &name);		std::shared_ptr<Symbol> find_local(const std::string &name);

	std::shared_ptr<Symbol> find(const std::string &name, size_t from = 0) const;		std::shared_ptr<Symbol> find(const std::string &name, size_t from = 0) const;

	};		};
	</cpp>		</cpp>

Root: /* The Symbol Table */

2015-04-13T23:45:54Z

The Symbol Table

@@ Line 24: / Line 24: @@
    class symbol_table {
    public:
      void push();
      void pop();
      bool insert(const std::string &name, std::shared_ptr<Symbol> symbol);
      bool replace_local(const std::string &name, std::shared_ptr<Symbol> symbol);
      bool replace(const std::string &name, std::shared_ptr<Symbol> symbol);
      std::shared_ptr<Symbol> find_local(const std::string &name);
      std::shared_ptr<Symbol> find(const std::string &name, size_t from = 0) const;
 };
 </cpp>
 == Type Checking: Using Visitors ==

Root at 14:33, 6 April 2015

2015-04-06T14:33:04Z

← Older revision		Revision as of 14:33, 6 April 2015
Line 126:		Line 126:
	* [[Semantic Analysis/Exercise 01\|Exercise 01]] - The "Let" language		* [[Semantic Analysis/Exercise 01\|Exercise 01]] - The "Let" language

	[[category:~~Compilers~~]]		[[category:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root: /* Exercises */

2014-05-05T19:18:05Z

Exercises

← Older revision		Revision as of 19:18, 5 May 2014
Line 124:		Line 124:
	== Exercises ==		== Exercises ==

	* [[Semantic Analysis/Exercise 01\|Exercise 01]] - "~~Simple~~" language		* [[Semantic Analysis/Exercise 01\|Exercise 01]] - The "Let" language

	[[category:Compilers]]		[[category:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root at 19:17, 5 May 2014

2014-05-05T19:17:07Z

← Older revision		Revision as of 19:17, 5 May 2014
Line 103:		Line 103:
	In the approach followed by CDK-based compilers, code generation is carried out by visitors that are responsible for traversing the abstract syntax tree and generate, evaluating each node. Node evaluation may depend on the specificities of the data types being manipulated, the simplest of which is the data type's size, important in all memory-related operations.		In the approach followed by CDK-based compilers, code generation is carried out by visitors that are responsible for traversing the abstract syntax tree and generate, evaluating each node. Node evaluation may depend on the specificities of the data types being manipulated, the simplest of which is the data type's size, important in all memory-related operations.

	== Type checking example: the Tiny language ==		== Examples ==
			=== Type checking example: the Tiny language ===

	The following example considers a simple grammar and performs the whole of the semantic analysis process and, finally, generates the corresponding C code. The semantic analysis process must account for variables (they must be declared before they can be used) and for their types (all types must be used correctly).		The following example considers a simple grammar and performs the whole of the semantic analysis process and, finally, generates the corresponding C code. The semantic analysis process must account for variables (they must be declared before they can be used) and for their types (all types must be used correctly).
Line 109:		Line 110:
	* [[Semantic Analysis/The Tiny language: semantic analysis example and C generation\|The Tiny language: semantic analysis example and C generation]]		* [[Semantic Analysis/The Tiny language: semantic analysis example and C generation\|The Tiny language: semantic analysis example and C generation]]

	== Type checking example: the Simple language ==		=== Type checking example: the Simple language ===

	The following example considers an evolution of Compact, called Simple. Where Compact forces some verification via syntactic analysis (thus, presenting low flexibility), Simple has a richer grammar and, consequently, admits constructions that may not be correct in what concerns types of operators, functions, and their arguments. Type checking in this case is built-in, since, without it, it would be impossible to guarantee the correctness of any expression.		The following example considers an evolution of Compact, called Simple. Where Compact forces some verification via syntactic analysis (thus, presenting low flexibility), Simple has a richer grammar and, consequently, admits constructions that may not be correct in what concerns types of operators, functions, and their arguments. Type checking in this case is built-in, since, without it, it would be impossible to guarantee the correctness of any expression.
Line 115:		Line 116:
	* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]		* [[Semantic Analysis/The Simple language: semantic analysis\|The Simple language: semantic analysis]]

	== Type checking example: the Compact language [obsolete]==		=== Type checking example: the Compact language [obsolete]===

	The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.		The following example presents an old version of the Compact compiler. This case is no longer relevant, but shows how an existing compiler can be extended.