让程序求解一个表达式如123+234*(12/2),应该如何出处理呢?不同的思路可能有不同的答案,这里用编译原理这把牛刀宰它。
整体思路:
词法分析->语法分析->语义分析
其中需要说明的是语义分析是包含在语法分析中的,因为用的是语法制导翻译方法。
0.文法
E->T E1
E1->op1|T fun1 E1|null
T->F T1
T1->op2 F fun1 T1| null
F->(E)|-F fun2|I
I->const fun3
op1->+fun4|-fun5
op2->*fun6|/fun6
1.词法分析
词法分析是比较简单,主要分为三类:
数字:0-9
界符:( )
运算符:+,-,*,/
建立词法分析表(只是举例和代码并不匹配):
由词法分析表驱动词法解析程序,效果如下:
token结构是:
type Token struct {
Kind int //类型
Content string //值
RowNum int //行数
}
[{1 123 0} {2 + 0} {1 234 0} {2 * 0} {3 ( 0} {1 12 0} {2 / 0} {1 2 0} {3 ) 0}]
2.语法分析
核心框图:
由文法规则获取first集和follow集,进而建立语法分析表:
var sParseTable = [8][8]string{
// + - * / const ( ) $
{"err", "T,E1", "err", "err", "T,E1", "T,E1", "err", "err"}, //E
{"op1,T,fun1,E1", "op1,T,fun1,E1", "err", "err", "err", "err", "null", "null"}, //E1
{"err", "F,T1", "err", "err", "F,T1", "F,T1", "err", "err"}, //T
{"null", "null", "op2,F,fun1,T1", "op2,F,fun1,T1", "err", "err", "null", "null"}, //T1
{"err", "-,F,fun2", "err", "err", "I", "(,E,)", "err", "err"}, //F
{"err", "err", "err", "err", "const,fun3", "err", "err", "err"}, //I
{"+,fun4", "-,fun5", "err", "err", "err", "err", "err", "err"}, //op1
{"err", "err", "*,fun6", "/,fun7", "err", "err", "err", "err"}, //op2
}
分析器核心程序:
func (c *Calc) Parse() bool {
iListPos := 0
var ival DataStack
for c.ParseStack.Len() != 0 && iListPos < len(c.TokenList) {
el := c.ParseStack.Back()
ival = el.Value.(DataStack)
c.ParseStack.Remove(el)
if ival.Kind == "VT" { //非终结符
icol := "$"
if c.TokenList[iListPos].Kind == TOKEN_KIND_CONST {
icol = "const"
} else if c.TokenList[iListPos].Kind == TOKEN_KIND_OPRATOR {
icol = c.TokenList[iListPos].Content
} else if c.TokenList[iListPos].Kind == TOKEN_KIND_SPLITE {
icol = c.TokenList[iListPos].Content
}
if v, ok := c.ParseTables[Pcell{ival.Data, icol}]; ok { //查询语法分析表
if v.Data == "err" {
log.Fatal("row,col:", ival.Data, c.TokenList[iListPos])
} else if v.Data == "null" {
continue
} else {
tmp := strings.Split(v.Data, ",")
for k, _ := range tmp {
re := tmp[len(tmp)-k-1]
kind := ""
if isVT(re) {
kind = "VT" //非终结
} else if isFUN(re) {
kind = "FUN" //语义部分
} else {
kind = "VN" //终结
}
ds := DataStack{
Data: re,
Kind: kind,
}
c.ParseStack.PushBack(ds) //反序入栈
}
}
} else {
log.Fatal("row,col:", ival.Data, c.TokenList[iListPos])
}
} else if ival.Kind == "VN" { //终结符
fmt.Println("VN:", ival)
iListPos += 1 //下一个输入流
} else if ival.Kind == "FUN" { //语义处理
fmt.Println("FUN:", ival)
switch ival.Data {
case "fun1":
c.fun1()
case "fun2":
c.fun2()
case "fun3":
c.fun3(c.TokenList[iListPos-1].Content)
case "fun4":
c.fun4()
case "fun5":
c.fun5()
case "fun6":
c.fun6()
case "fun7":
c.fun7()
}
// fmt.Println("FUN END:", c.OprateDataStack.Back().Value, c.OprateSplitStack.Back().Value)
}
ps := make([]string, 0)
for i := c.ParseStack.Back(); i != nil; i = i.Prev() {
ps = append(ps, i.Value.(DataStack).Data)
}
fmt.Println("ps:", ps)
}
if c.ParseStack.Len() == 0 && iListPos == len(c.TokenList) {
c.Result = c.OprateDataStack.Back().Value.(string)
return true
} else {
return false
}
}
现在代码还有点乱,等整理后会上传至github。有词法分析和语法制导翻译的知识可以基本写一个简单的avr汇编器了。
]]>go语言开发的avr汇编器之词法分析已完成,主要流程是建立词法的状态转换表,表建成工作基本完成80%,整个流程就是表驱动。
https://whycan.com/files/members/1315/Screenshot191800.png
( ఠൠఠ )ノ
]]>;
; ***********************************
; * (Add program task here) *
; * (Add AVR type and version here) *
; * (C)2019 by Gerhard Schmidt *
; ***********************************
;
.nolist
.include "tn13adef.inc" ; Define device ATtiny13A
.list
;
; **********************************
; H A R D W A R E
; **********************************
;
; (F2 adds ASCII pin-out for device here)
;
; **********************************
; P O R T S A N D P I N S
; **********************************
;
; (Add symbols for all ports and port pins with ".equ" here)
; (e.g. .equ pDirD = DDRB ; Define a direction port
; or
; .equ bMyPinO = PORTB0 ; Define an output pin)
;
; **********************************
; A D J U S T A B L E C O N S T
; **********************************
;
; (Add all user adjustable constants here, e.g.)
.equ clock=9600000 ; Define the clock frequency
.equ baudRate=115200
.equ TX_DELAY = (clock / baudRate - 9) / 3;
;.equ cycle_t = 1000000 / clock
.equ wait_cnt_10us = 10 ;10 / cycle_t / 10
;
; **********************************
; F I X & D E R I V. C O N S T
; **********************************
;
; (Add symbols for fixed and derived constants here)
;
; **********************************
; R E G I S T E R S
; **********************************
;
; free: R0 to R14
.def rSreg = R15 ; Save/Restore status port
.def rmp = R16 ; Define multipurpose register
; free: R17 to R29
; used: R31:R30 = Z for ...
;
.def TX_BITS_NBR_TMP = R18
.def WAIT_NBR_TMP = R19
.def BYTE_TO_TRANSMIT = R24
.def WAIT_NBR = R22
; **********************************
; S R A M
; **********************************
;
.dseg
.org SRAM_START
; (Add labels for SRAM locations here, e.g.
; sLabel1:
; .byte 16 ; Reserve 16 bytes)
;
; **********************************
; C O D E
; **********************************
;
.cseg
.org 000000
;
; **********************************
; R E S E T & I N T - V E C T O R S
; **********************************
rjmp Main ; Reset vector
reti ; INT0
reti ; PCI0
reti ; OVF0
reti ; ERDY
reti ; ACI
reti ; OC0A
reti ; OC0B
reti ; WDT
reti ; ADCC
;
; **********************************
; I N T - S E R V I C E R O U T .
; **********************************
;
; (Add all interrupt service routines here)
;
; **********************************
; M A I N P R O G R A M I N I T
; **********************************
;
Main:
ldi rmp,Low(RAMEND)
out SPL,rmp ; Init LSB stack pointer
; ...
; sei ; Enable interrupts
;
; **********************************
; P R O G R A M L O O P
; **********************************
;
ldi WAIT_NBR,TX_DELAY
ldi BYTE_TO_TRANSMIT,0x0A
rcall SerialAsmTx_4
Loop:
ldi WAIT_NBR,TX_DELAY
ldi BYTE_TO_TRANSMIT,0x0A
rcall SerialAsmTx_4
ldi r28,50
rcall delay_500ms
rjmp loop
;
; End of source code
SerialAsmTx_4:
cli
sbi DDRB, PB4
ldi TX_BITS_NBR_TMP, 10
com BYTE_TO_TRANSMIT
TxLoop_4:
brcc Tx1_4
cbi PORTB, PB4
Tx1_4:
brcs TxDone_4
sbi PORTB, PB4
TxDone_4:
mov WAIT_NBR_TMP, WAIT_NBR
TxDelay_4:
dec WAIT_NBR_TMP
brne TxDelay_4
lsr BYTE_TO_TRANSMIT
dec TX_BITS_NBR_TMP
brne TxLoop_4
reti
;10 cycles,per loop
delay_500ms:
ldi r25,wait_cnt_10us
ldi r26,100
ldi r27,10
loop1:
nop
nop
nop
nop
nop
nop
nop
dec r25
brne loop1
dec r26
ldi r25, wait_cnt_10us
brne loop1
ldi r26,100
dec r27
brne loop1
ldi r27,10
dec r28
brne loop1
ret
;
; (Add Copyright information here, e.g.
; .db "(C)2019 by Gerhard Schmidt " ; Source code readable
; .db "C(2)10 9ybG reahdrS hcimtd " ; Machine code format
;
]]>
首先介绍一下用到的工具:
1.atmel studio,主要用它编译和仿真汇编代码
2.硬件,一个avr最小系统,我选择attiny13,研究汇编够用了
3.烧写器usb isp,以及烧写工具智峰下载器
4.avr汇编指令集手册,以及attiny13的手册
开篇上点灯程序:
.cseg
.org $0
rjmp start
.org $000A
start:
sbi DDRB,DDB0
sbi PORTB,PB0
Loop:
rjmp loop
机器码对照:
.cseg
.org $0
000000 c009 rjmp start
.org $000A
start:
00000a 9ab8 sbi DDRB,DDB0
00000b 9ac0 sbi PORTB,PB0
Loop:
00000c cfff rjmp loop
hex格式
:020000020000FC
:0200000009C035
:06001400B89AC09AFFCF6C
:00000001FF
flash memery快照:
prog 0x0000 09 c0 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff b8 9a c0 9a
prog 0x0018 ff cf ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
hex格式解释:
数据个数 地址 类型 数据 crc校验
: 00 0000 00 000000... 00
下载器使用hex文件烧录数据到avr,中间经过了解析hex文件的过程。主要是取出机器码并烧录到flash。
avr的汇编格式是:
操作码---操作数/地址/空---操作数/地址/空
整条指令是16位或是32位(32位很少)
avr整个工作过程是,从mcu上电开始,pc指向flash的0地址,开始取指-执行重复下去,直至结束。我们每天使用的电脑办公、手机刷视频,在cpu看来都是一堆01010101。
我们可以用汇编开发mcu,也可以直接用机器码开发。上古计算机就是机器码编程,那时候是没有falsh,直接把01代码用纸带打孔的方式来表示,也就是说纸带相当于falsh。即使现在用机器码开发,比那时候也简单多了,直接在电脑上查询寄存器的地址并转为相应的机器码,然后烧进falsh即可。
]]>