An educational interpreter demonstrating dynamic scoping through runtime call stack resolution
This compiler implements dynamic scoping—a variable resolution mechanism where names are resolved based on the runtime call stack rather than lexical structure. Built with Flex, Bison, and C++, it serves as an educational tool for understanding alternative scoping strategies in programming language design.
Core Technologies
┌─────────────┬────────────────────────────────────────┐
│ Flex │ Lexical analysis and tokenization │
│ Bison │ Syntax analysis and grammar parsing │
│ C++ │ AST construction and execution engine │
└─────────────┴────────────────────────────────────────┘
In dynamic scoping, variable resolution follows the call stack at runtime, not the textual structure at compile time.
graph TD
A[Variable Reference] --> B{Check Current Scope}
B -->|Found| C[Return Value]
B -->|Not Found| D[Pop Stack Frame]
D --> E{More Frames?}
E -->|Yes| B
E -->|No| F[Error: Undefined]
style A fill:#4C566A,stroke:#D8DEE9,color:#ECEFF4
style C fill:#A3BE8C,stroke:#D8DEE9,color:#2E3440
style F fill:#BF616A,stroke:#D8DEE9,color:#ECEFF4
| Aspect | Dynamic Scoping | Lexical Scoping |
|---|---|---|
| Resolution Time | Runtime | Compile Time |
| Search Strategy | Call stack traversal | Syntactic hierarchy |
| Visibility Rules | Caller's environment visible | Only defined scope visible |
| Predictability | Context-dependent | Context-independent |
The following program demonstrates how variable resolution changes based on the execution context:
a = 10;
status = 1;
func sub {
if (status) {
print a;
}
}
func principal {
a = 999;
status = 1;
sub();
}
print a;
principal();
status = 0;
sub(); sequenceDiagram
autonumber
participant G as Global Scope<br/>[a=10, status=1]
participant P as principal()<br/>[a=999, status=1]
participant S as sub()<br/>[no locals]
Note over G: First print statement
G->>G: print a → 10
Note over G,P: Call principal()
G->>P: push scope
P->>P: a = 999, status = 1
Note over P,S: Call sub() from principal
P->>S: push scope
Note over S: Lookup 'a' in stack
S->>P: Found a = 999
S->>S: print a → 999
S->>P: pop scope
P->>G: pop scope
G->>G: status = 0
Note over G,S: Call sub() from global
G->>S: push scope
Note over S: status = 0, condition fails
S->>G: pop scope (no output)
Output
10
999
The value printed by sub() depends entirely on who called it, not where it was defined.
dynamic-scope-compiler/
│
├── include/
│ ├── ast.h # AST node definitions
│ └── environment.h # Scope stack interface
│
├── src/
│ ├── lexer.l # Token specification
│ ├── parser.y # Grammar rules and AST construction
│ ├── ast.cpp # AST node implementations
│ └── environment.cpp # Dynamic scope management
│
├── tests/
│ └── test.ds # Test programs
│
├── examples/ # Additional demonstrations
│
├── Makefile # Build configuration
└── README.md
Ensure you have the required build tools:
# Debian/Ubuntu
sudo apt-get install build-essential flex bison g++
# macOS (Homebrew)
brew install flex bison gcc make
# Fedora/RHEL
sudo dnf install gcc-c++ flex bison make# Clone repository
git clone https://github.com/yourusername/dynamic-scope-compiler.git
cd dynamic-scope-compiler
# Compile
make
# Verify installation
./compiler --version# Execute test file
./compiler < tests/test.ds
# Run custom program
./compiler < myprogram.ds
# Interactive mode (if supported)
./compilerVariable Assignment
x = 42;
flag = true;Function Definition
func functionName {
// Function body
}Conditional Execution
if (condition) {
// Executed if condition is truthy
}Function Invocation
functionName();Output Statement
print expression;flowchart LR
A[Source Code] --> B[Lexer]
B --> C[Token Stream]
C --> D[Parser]
D --> E[AST]
E --> F[Interpreter]
F --> G[Environment Stack]
G --> H[Execution Result]
style A fill:#4C566A,stroke:#D8DEE9,color:#ECEFF4
style E fill:#5E81AC,stroke:#D8DEE9,color:#ECEFF4
style G fill:#88C0D0,stroke:#D8DEE9,color:#2E3440
style H fill:#A3BE8C,stroke:#D8DEE9,color:#2E3440
| Component | Files | Purpose |
|---|---|---|
| Lexical Analyzer | lexer.l |
Converts character stream into tokens (identifiers, keywords, operators) |
| Syntax Analyzer | parser.y |
Validates grammar and constructs abstract syntax tree |
| AST | ast.h/cpp |
Tree structure representing program semantics and evaluation logic |
| Environment | environment.h/cpp |
Manages scope stack for dynamic variable resolution |
The environment maintains a stack of hash maps. On variable lookup:
- Search the topmost (current) scope
- If not found, move to the previous stack frame
- Repeat until found or stack exhausted
- Throw error if undefined
This contrasts with lexical scoping, where the search follows the syntactic nesting of code blocks.
This project addresses key concepts in compiler theory:
| Lexical Analysis | Regular expressions and finite automata |
| Syntax Analysis | Context-free grammars and parse trees |
| Semantic Analysis | Scope resolution and type systems |
| Runtime Systems | Call stacks and environment management |
| Language Design | Scoping strategies and their implications |
MIT License
Copyright (c) 2024 Pedro V. Santos
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
Pedro V. Santos
Computer Science Student
Developed for academic purposes in compiler construction