lexer.go 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "fmt"
  12. "regexp"
  13. "strconv"
  14. "strings"
  15. "unicode"
  16. "unicode/utf8"
  17. "devt.de/krotik/common/stringutil"
  18. )
  19. /*
  20. LexToken represents a token which is returned by the lexer.
  21. */
  22. type LexToken struct {
  23. ID LexTokenID // Token kind
  24. Pos int // Starting position (in runes)
  25. Val string // Token value
  26. Lline int // Line in the input this token appears
  27. Lpos int // Position in the input line this token appears
  28. }
  29. /*
  30. PosString returns the position of this token in the origianl input as a string.
  31. */
  32. func (t LexToken) PosString() string {
  33. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  34. }
  35. /*
  36. String returns a string representation of a token.
  37. */
  38. func (t LexToken) String() string {
  39. switch {
  40. case t.ID == TokenEOF:
  41. return "EOF"
  42. case t.ID == TokenError:
  43. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  44. case t.ID == TokenName:
  45. return fmt.Sprintf("<%s>", t.Val)
  46. case t.ID == TokenStringValue:
  47. return fmt.Sprintf("\"%s\"", t.Val)
  48. case t.ID == TokenIntValue:
  49. return fmt.Sprintf("int(%s)", t.Val)
  50. case t.ID == TokenFloatValue:
  51. return fmt.Sprintf("flt(%s)", t.Val)
  52. }
  53. return fmt.Sprintf("%s", t.Val)
  54. }
  55. /*
  56. SymbolMap is a map of special symbols
  57. */
  58. var SymbolMap = map[string]LexTokenID{
  59. "!": TokenPunctuator,
  60. "$": TokenPunctuator,
  61. "(": TokenPunctuator,
  62. ")": TokenPunctuator,
  63. ":": TokenPunctuator,
  64. "=": TokenPunctuator,
  65. "@": TokenPunctuator,
  66. "[": TokenPunctuator,
  67. "]": TokenPunctuator,
  68. "{": TokenPunctuator,
  69. "|": TokenPunctuator,
  70. "}": TokenPunctuator,
  71. // "..." Is checked as a special case
  72. }
  73. // Lexer
  74. // =====
  75. /*
  76. RuneEOF is a special rune which represents the end of the input
  77. */
  78. const RuneEOF = -1
  79. /*
  80. RuneComma is the rune for a comma
  81. */
  82. const RuneComma = ','
  83. /*
  84. Function which represents the current state of the lexer and returns the next state
  85. */
  86. type lexFunc func() lexFunc
  87. /*
  88. Lexer data structure
  89. */
  90. type lexer struct {
  91. name string // Name to identify the input
  92. input string // Input string of the lexer
  93. pos int // Current rune pointer
  94. line int // Current line pointer
  95. lastnl int // Last newline position
  96. width int // Width of last rune
  97. start int // Start position of the current red token
  98. tokens chan LexToken // Channel for lexer output
  99. }
  100. /*
  101. Lex lexes a given input. Returns a channel which contains tokens.
  102. */
  103. func Lex(name string, input string) chan LexToken {
  104. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  105. go l.run()
  106. return l.tokens
  107. }
  108. /*
  109. LexToList lexes a given input. Returns a list of tokens.
  110. */
  111. func LexToList(name string, input string) []LexToken {
  112. var tokens []LexToken
  113. for t := range Lex(name, input) {
  114. tokens = append(tokens, t)
  115. }
  116. return tokens
  117. }
  118. /*
  119. run is the main loop of the lexer.
  120. */
  121. func (l *lexer) run() {
  122. if l.skipWhiteSpace() {
  123. for state := l.lexToken; state != nil; {
  124. state = state()
  125. if !l.skipWhiteSpace() {
  126. break
  127. }
  128. }
  129. }
  130. close(l.tokens)
  131. }
  132. /*
  133. next returns the next rune in the input and advances the current rune pointer if the
  134. peek value is -1 or smaller. If the peek value is 0 or greater then the nth token from the current
  135. position is returned without advancing the current rune pointer.
  136. */
  137. func (l *lexer) next(peek int) rune {
  138. var r rune
  139. var w, peekw int
  140. // Check if we reached the end
  141. if int(l.pos) >= len(l.input) {
  142. return RuneEOF
  143. }
  144. // Decode the next rune
  145. peeklen := 1 + peek
  146. if peeklen < 1 {
  147. peeklen = 1
  148. }
  149. for i := 0; i < peeklen; i++ {
  150. r, w = utf8.DecodeRuneInString(l.input[l.pos+peekw:])
  151. peekw += w
  152. }
  153. if peek == -1 {
  154. l.width = w
  155. l.pos += l.width
  156. }
  157. return r
  158. }
  159. /*
  160. hasSequence checks if the next characters are of the following sequence.
  161. */
  162. func (l *lexer) hasSequence(s string) bool {
  163. runes := stringutil.StringToRuneSlice(s)
  164. for i := 0; i < len(runes); i++ {
  165. if l.next(i) != runes[i] {
  166. return false
  167. }
  168. }
  169. return true
  170. }
  171. /*
  172. startNew starts a new token.
  173. */
  174. func (l *lexer) startNew() {
  175. l.start = l.pos
  176. }
  177. /*
  178. emitTokenAndValue passes a token with a given value back to the client.
  179. */
  180. func (l *lexer) emitToken(i LexTokenID, val string) {
  181. if l.tokens != nil {
  182. l.tokens <- LexToken{i, l.start, val, l.line + 1, l.start - l.lastnl + 1}
  183. }
  184. }
  185. // State functions
  186. // ===============
  187. /*
  188. lexToken is the main entry function for the lexer.
  189. */
  190. func (l *lexer) lexToken() lexFunc {
  191. l.startNew()
  192. l.lexTextBlock()
  193. token := l.input[l.start:l.pos]
  194. // Check for Comment - @spec 2.1.4, 2.1.7
  195. if token == "#" {
  196. return l.skipRestOfLine()
  197. }
  198. // Lexical tokens - @spec 2.1.6
  199. // Check for String
  200. if token == "\"" {
  201. return l.lexStringValue()
  202. }
  203. // Check for Punctuator - @spec 2.1.8
  204. if _, ok := SymbolMap[token]; ok || token == "..." {
  205. l.emitToken(TokenPunctuator, token)
  206. return l.lexToken
  207. }
  208. // Check for Name - @spec 2.1.9
  209. isName, _ := regexp.MatchString("^[_A-Za-z][_0-9A-Za-z]*$", token)
  210. if isName {
  211. l.emitToken(TokenName, token)
  212. return l.lexToken
  213. }
  214. // Check for IntValue - @spec 2.9.1
  215. isZero, _ := regexp.MatchString("^-?0$", token)
  216. isInt, _ := regexp.MatchString("^-?[1-9][0-9]*$", token)
  217. if isZero || isInt {
  218. l.emitToken(TokenIntValue, token)
  219. return l.lexToken
  220. }
  221. // Check for FloatValue - @spec 2.9.2
  222. isFloat1, _ := regexp.MatchString("^[0-9]*\\.[0-9]*$", token)
  223. isFloat2, _ := regexp.MatchString("^[0-9][eE][+-]?[0-9]*$", token)
  224. isFloat3, _ := regexp.MatchString("^[0-9]*\\.[0-9][eE][+-]?[0-9]*$", token)
  225. if isFloat1 || isFloat2 || isFloat3 {
  226. l.emitToken(TokenFloatValue, strings.ToLower(token))
  227. return l.lexToken
  228. }
  229. // Everything else is an error
  230. l.emitToken(TokenError, token)
  231. return l.lexToken
  232. }
  233. /*
  234. lexTextBlock lexes a block of text without whitespaces. Interprets
  235. optionally all one or two letter tokens.
  236. */
  237. func (l *lexer) lexTextBlock() {
  238. r := l.next(0)
  239. // Check if we start with a known symbol
  240. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok || r == '#' || r == '"' {
  241. l.next(-1)
  242. return
  243. } else if r == '.' && l.hasSequence("...") {
  244. l.next(-1)
  245. l.next(-1)
  246. l.next(-1)
  247. return
  248. }
  249. for !l.isIgnoredRune(r) {
  250. l.next(-1)
  251. r = l.next(0)
  252. // Check if we find a token in the block
  253. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok || r == '#' || r == '"' {
  254. return
  255. } else if r == '.' && l.hasSequence("...") {
  256. return
  257. }
  258. }
  259. }
  260. /*
  261. lexStringValue lexes a string value either as a simple string or a block string.
  262. Values can be declared in different ways:
  263. " ... " A normal string (escape sequences are interpreted)
  264. """ ... """ A multi-line string (escape sequences are not interpreted)
  265. */
  266. func (l *lexer) lexStringValue() lexFunc {
  267. var isEnd func(rune) bool
  268. // String value lexing - @spec 2.9.4
  269. // Lookahead 2 tokens
  270. r1 := l.next(0)
  271. r2 := l.next(1)
  272. isBlockString := r1 == '"' && r2 == '"'
  273. if isBlockString {
  274. // Consume the initial quotes for blockstrings
  275. l.next(-1)
  276. l.next(-1)
  277. isEnd = func(r rune) bool {
  278. r1 := l.next(0)
  279. r2 := l.next(1)
  280. return r == '"' && r1 == '"' && r2 == '"'
  281. }
  282. } else {
  283. isEnd = func(r rune) bool {
  284. return r == '"'
  285. }
  286. }
  287. r := l.next(-1)
  288. lLine := l.line
  289. lLastnl := l.lastnl
  290. for !isEnd(r) {
  291. if r == '\n' {
  292. lLine++
  293. lLastnl = l.pos
  294. }
  295. r = l.next(-1)
  296. if r == RuneEOF {
  297. l.emitToken(TokenError, "EOF inside quotes")
  298. return nil
  299. }
  300. }
  301. if !isBlockString {
  302. val := l.input[l.start+1 : l.pos-1]
  303. s, err := strconv.Unquote("\"" + val + "\"")
  304. if err != nil {
  305. l.emitToken(TokenError, "Could not interpret escape sequence: "+err.Error())
  306. return nil
  307. }
  308. l.emitToken(TokenStringValue, s)
  309. } else {
  310. // Consume the final quotes for blockstrings
  311. l.next(-1)
  312. l.next(-1)
  313. token := l.input[l.start+3 : l.pos-3]
  314. // Since block strings represent freeform text often used in indented
  315. // positions, the string value semantics of a block string excludes uniform
  316. // indentation and blank initial and trailing lines
  317. // (from spec about 'Block Strings')
  318. token = stringutil.StripUniformIndentation(token)
  319. token = stringutil.TrimBlankLines(token)
  320. l.emitToken(TokenStringValue, token)
  321. }
  322. // Set newline
  323. l.line = lLine
  324. l.lastnl = lLastnl
  325. return l.lexToken
  326. }
  327. /*
  328. isIgnoredRune checks if a given rune should be ignored.
  329. */
  330. func (l *lexer) isIgnoredRune(r rune) bool {
  331. // Ignored tokens - @spec 2.1.1, 2.1.2, 2.1.3, 2.1.3, 2.1.5, 2.1.7
  332. return unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF ||
  333. r == RuneComma || r == '\ufeff'
  334. }
  335. /*
  336. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  337. reaches EOF while skipping whitespaces.
  338. */
  339. func (l *lexer) skipWhiteSpace() bool {
  340. r := l.next(0)
  341. for l.isIgnoredRune(r) {
  342. if r == '\n' {
  343. l.line++
  344. l.lastnl = l.pos
  345. }
  346. l.next(-1)
  347. if r == RuneEOF {
  348. l.startNew()
  349. l.start--
  350. l.emitToken(TokenEOF, "")
  351. return false
  352. }
  353. r = l.next(0)
  354. }
  355. return true
  356. }
  357. /*
  358. skipRestOfLine skips all characters until the next newline character.
  359. */
  360. func (l *lexer) skipRestOfLine() lexFunc {
  361. r := l.next(-1)
  362. for r != '\n' && r != RuneEOF {
  363. r = l.next(-1)
  364. }
  365. if r == RuneEOF {
  366. return nil
  367. }
  368. l.line++
  369. l.lastnl = l.pos - 1
  370. return l.lexToken
  371. }