lexer.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794
  1. /*
  2. * ECAL
  3. *
  4. * Copyright 2020 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the MIT
  7. * License, If a copy of the MIT License was not distributed with this
  8. * file, You can obtain one at https://opensource.org/licenses/MIT.
  9. */
  10. package parser
  11. import (
  12. "bytes"
  13. "encoding/json"
  14. "fmt"
  15. "regexp"
  16. "strconv"
  17. "strings"
  18. "unicode"
  19. "unicode/utf8"
  20. )
  21. /*
  22. NamePattern is the pattern for valid names.
  23. */
  24. var NamePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  25. /*
  26. numberPattern is a hint pattern for numbers.
  27. */
  28. var numberPattern = regexp.MustCompile("^[0-9].*$")
  29. /*
  30. LexToken represents a token which is returned by the lexer.
  31. */
  32. type LexToken struct {
  33. ID LexTokenID // Token kind
  34. Pos int // Starting position (in bytes)
  35. Val string // Token value
  36. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  37. AllowEscapes bool // Flag if the value did interpret escape charaters
  38. Lsource string // Input source label (e.g. filename)
  39. Lline int // Line in the input this token appears
  40. Lpos int // Position in the input line this token appears
  41. }
  42. /*
  43. NewLexTokenInstance creates a new LexToken object instance from given LexToken values.
  44. */
  45. func NewLexTokenInstance(t LexToken) *LexToken {
  46. return &LexToken{
  47. t.ID,
  48. t.Pos,
  49. t.Val,
  50. t.Identifier,
  51. t.AllowEscapes,
  52. t.Lsource,
  53. t.Lline,
  54. t.Lpos,
  55. }
  56. }
  57. /*
  58. Equals checks if this LexToken equals another LexToken. Returns also a message describing
  59. what is the found difference.
  60. */
  61. func (t LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  62. var res = true
  63. var msg = ""
  64. if t.ID != other.ID {
  65. res = false
  66. msg += fmt.Sprintf("ID is different %v vs %v\n", t.ID, other.ID)
  67. }
  68. if !ignorePosition && t.Pos != other.Pos {
  69. res = false
  70. msg += fmt.Sprintf("Pos is different %v vs %v\n", t.Pos, other.Pos)
  71. }
  72. if t.Val != other.Val {
  73. res = false
  74. msg += fmt.Sprintf("Val is different %v vs %v\n", t.Val, other.Val)
  75. }
  76. if t.Identifier != other.Identifier {
  77. res = false
  78. msg += fmt.Sprintf("Identifier is different %v vs %v\n", t.Identifier, other.Identifier)
  79. }
  80. if !ignorePosition && t.Lline != other.Lline {
  81. res = false
  82. msg += fmt.Sprintf("Lline is different %v vs %v\n", t.Lline, other.Lline)
  83. }
  84. if !ignorePosition && t.Lpos != other.Lpos {
  85. res = false
  86. msg += fmt.Sprintf("Lpos is different %v vs %v\n", t.Lpos, other.Lpos)
  87. }
  88. if msg != "" {
  89. var buf bytes.Buffer
  90. out, _ := json.MarshalIndent(t, "", " ")
  91. buf.WriteString(string(out))
  92. buf.WriteString("\nvs\n")
  93. out, _ = json.MarshalIndent(other, "", " ")
  94. buf.WriteString(string(out))
  95. msg = fmt.Sprintf("%v%v", msg, buf.String())
  96. }
  97. return res, msg
  98. }
  99. /*
  100. PosString returns the position of this token in the origianl input as a string.
  101. */
  102. func (t LexToken) PosString() string {
  103. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  104. }
  105. /*
  106. String returns a string representation of a token.
  107. */
  108. func (t LexToken) String() string {
  109. prefix := ""
  110. if !t.Identifier {
  111. prefix = "v:" // Value is not an identifier
  112. }
  113. switch {
  114. case t.ID == TokenEOF:
  115. return "EOF"
  116. case t.ID == TokenError:
  117. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  118. case t.ID == TokenPRECOMMENT:
  119. return fmt.Sprintf("/* %s */", t.Val)
  120. case t.ID == TokenPOSTCOMMENT:
  121. return fmt.Sprintf("# %s", t.Val)
  122. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  123. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  124. case t.ID > TOKENodeKEYWORDS:
  125. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  126. case len(t.Val) > 20:
  127. // Special case for very long values
  128. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  129. }
  130. return fmt.Sprintf("%s%q", prefix, t.Val)
  131. }
  132. // Meta data interface
  133. /*
  134. Type returns the meta data type.
  135. */
  136. func (t LexToken) Type() string {
  137. if t.ID == TokenPRECOMMENT {
  138. return MetaDataPreComment
  139. } else if t.ID == TokenPOSTCOMMENT {
  140. return MetaDataPostComment
  141. }
  142. return MetaDataGeneral
  143. }
  144. /*
  145. Value returns the meta data value.
  146. */
  147. func (t LexToken) Value() string {
  148. return t.Val
  149. }
  150. /*
  151. KeywordMap is a map of keywords - these require spaces between them
  152. */
  153. var KeywordMap = map[string]LexTokenID{
  154. // Assign statement
  155. "let": TokenLET,
  156. // Import statement
  157. "import": TokenIMPORT,
  158. "as": TokenAS,
  159. // Sink definition
  160. "sink": TokenSINK,
  161. "kindmatch": TokenKINDMATCH,
  162. "scopematch": TokenSCOPEMATCH,
  163. "statematch": TokenSTATEMATCH,
  164. "priority": TokenPRIORITY,
  165. "suppresses": TokenSUPPRESSES,
  166. // Function definition
  167. "func": TokenFUNC,
  168. "return": TokenRETURN,
  169. // Boolean operators
  170. "and": TokenAND,
  171. "or": TokenOR,
  172. "not": TokenNOT,
  173. // String operators
  174. "like": TokenLIKE,
  175. "hasprefix": TokenHASPREFIX,
  176. "hassuffix": TokenHASSUFFIX,
  177. // List operators
  178. "in": TokenIN,
  179. "notin": TokenNOTIN,
  180. // Constant terminals
  181. "false": TokenFALSE,
  182. "true": TokenTRUE,
  183. "null": TokenNULL,
  184. // Conditional statements
  185. "if": TokenIF,
  186. "elif": TokenELIF,
  187. "else": TokenELSE,
  188. // Loop statements
  189. "for": TokenFOR,
  190. "break": TokenBREAK,
  191. "continue": TokenCONTINUE,
  192. // Try block
  193. "try": TokenTRY,
  194. "except": TokenEXCEPT,
  195. "finally": TokenFINALLY,
  196. // Mutex block
  197. "mutex": TokenMUTEX,
  198. }
  199. /*
  200. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  201. Symbols can be maximal 2 characters long.
  202. */
  203. var SymbolMap = map[string]LexTokenID{
  204. // Condition operators
  205. ">=": TokenGEQ,
  206. "<=": TokenLEQ,
  207. "!=": TokenNEQ,
  208. "==": TokenEQ,
  209. ">": TokenGT,
  210. "<": TokenLT,
  211. // Grouping symbols
  212. "(": TokenLPAREN,
  213. ")": TokenRPAREN,
  214. "[": TokenLBRACK,
  215. "]": TokenRBRACK,
  216. "{": TokenLBRACE,
  217. "}": TokenRBRACE,
  218. // Separators
  219. ".": TokenDOT,
  220. ",": TokenCOMMA,
  221. ";": TokenSEMICOLON,
  222. // Grouping
  223. ":": TokenCOLON,
  224. "=": TokenEQUAL,
  225. // Arithmetic operators
  226. "+": TokenPLUS,
  227. "-": TokenMINUS,
  228. "*": TokenTIMES,
  229. "/": TokenDIV,
  230. "//": TokenDIVINT,
  231. "%": TokenMODINT,
  232. // Assignment statement
  233. ":=": TokenASSIGN,
  234. }
  235. // Lexer
  236. // =====
  237. /*
  238. RuneEOF is a special rune which represents the end of the input
  239. */
  240. const RuneEOF = -1
  241. /*
  242. Function which represents the current state of the lexer and returns the next state
  243. */
  244. type lexFunc func(*lexer) lexFunc
  245. /*
  246. Lexer data structure
  247. */
  248. type lexer struct {
  249. name string // Name to identify the input
  250. input string // Input string of the lexer
  251. pos int // Current rune pointer
  252. line int // Current line pointer
  253. lastnl int // Last newline position
  254. width int // Width of last rune
  255. start int // Start position of the current red token
  256. tokens chan LexToken // Channel for lexer output
  257. }
  258. /*
  259. Lex lexes a given input. Returns a channel which contains tokens.
  260. */
  261. func Lex(name string, input string) chan LexToken {
  262. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  263. go l.run()
  264. return l.tokens
  265. }
  266. /*
  267. LexToList lexes a given input. Returns a list of tokens.
  268. */
  269. func LexToList(name string, input string) []LexToken {
  270. var tokens []LexToken
  271. for t := range Lex(name, input) {
  272. tokens = append(tokens, t)
  273. }
  274. return tokens
  275. }
  276. /*
  277. Main loop of the lexer.
  278. */
  279. func (l *lexer) run() {
  280. if skipWhiteSpace(l) {
  281. for state := lexToken; state != nil; {
  282. state = state(l)
  283. if !skipWhiteSpace(l) {
  284. break
  285. }
  286. }
  287. }
  288. close(l.tokens)
  289. }
  290. /*
  291. next returns the next rune in the input and advances the current rune pointer
  292. if peek is 0. If peek is >0 then the nth character is returned without advancing
  293. the rune pointer.
  294. */
  295. func (l *lexer) next(peek int) rune {
  296. // Check if we reached the end
  297. if int(l.pos) >= len(l.input) {
  298. return RuneEOF
  299. }
  300. // Decode the next rune
  301. pos := l.pos
  302. if peek > 0 {
  303. pos += peek - 1
  304. }
  305. r, w := utf8.DecodeRuneInString(l.input[pos:])
  306. if peek == 0 {
  307. l.width = w
  308. l.pos += l.width
  309. }
  310. return r
  311. }
  312. /*
  313. backup sets the pointer one rune back. Can only be called once per next call.
  314. */
  315. func (l *lexer) backup(width int) {
  316. if width == 0 {
  317. width = l.width
  318. }
  319. l.pos -= width
  320. }
  321. /*
  322. startNew starts a new token.
  323. */
  324. func (l *lexer) startNew() {
  325. l.start = l.pos
  326. }
  327. /*
  328. emitToken passes a token back to the client.
  329. */
  330. func (l *lexer) emitToken(t LexTokenID) {
  331. if t == TokenEOF {
  332. l.emitTokenAndValue(t, "", false, false)
  333. return
  334. }
  335. if l.tokens != nil {
  336. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false, false, l.name,
  337. l.line + 1, l.start - l.lastnl + 1}
  338. }
  339. }
  340. /*
  341. emitTokenAndValue passes a token with a given value back to the client.
  342. */
  343. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool, allowEscapes bool) {
  344. if l.tokens != nil {
  345. l.tokens <- LexToken{t, l.start, val, identifier, allowEscapes, l.name, l.line + 1, l.start - l.lastnl + 1}
  346. }
  347. }
  348. /*
  349. emitError passes an error token back to the client.
  350. */
  351. func (l *lexer) emitError(msg string) {
  352. if l.tokens != nil {
  353. l.tokens <- LexToken{TokenError, l.start, msg, false, false, l.name, l.line + 1, l.start - l.lastnl + 1}
  354. }
  355. }
  356. // Helper functions
  357. // ================
  358. /*
  359. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  360. reaches EOF while skipping whitespaces.
  361. */
  362. func skipWhiteSpace(l *lexer) bool {
  363. r := l.next(0)
  364. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  365. if r == '\n' {
  366. l.line++
  367. l.lastnl = l.pos
  368. }
  369. r = l.next(0)
  370. if r == RuneEOF {
  371. l.emitToken(TokenEOF)
  372. return false
  373. }
  374. }
  375. l.backup(0)
  376. return true
  377. }
  378. /*
  379. lexTextBlock lexes a block of text without whitespaces. Interprets
  380. optionally all one or two letter tokens.
  381. */
  382. func lexTextBlock(l *lexer, interpretToken bool) {
  383. r := l.next(0)
  384. if interpretToken {
  385. // Check if we start with a known symbol
  386. nr := l.next(1)
  387. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  388. l.next(0)
  389. return
  390. }
  391. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  392. return
  393. }
  394. }
  395. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  396. if interpretToken {
  397. // Check if we find a token in the block
  398. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  399. l.backup(0)
  400. return
  401. }
  402. nr := l.next(1)
  403. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  404. l.backup(0)
  405. return
  406. }
  407. }
  408. r = l.next(0)
  409. }
  410. if r != RuneEOF {
  411. l.backup(0)
  412. }
  413. }
  414. /*
  415. lexNumberBlock lexes a block potentially containing a number.
  416. */
  417. func lexNumberBlock(l *lexer) {
  418. r := l.next(0)
  419. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  420. if !unicode.IsNumber(r) && r != '.' {
  421. if r == 'e' {
  422. l1 := l.next(1)
  423. l2 := l.next(2)
  424. if l1 != '+' || !unicode.IsNumber(l2) {
  425. break
  426. }
  427. l.next(0)
  428. l.next(0)
  429. } else {
  430. break
  431. }
  432. }
  433. r = l.next(0)
  434. }
  435. if r != RuneEOF {
  436. l.backup(0)
  437. }
  438. }
  439. // State functions
  440. // ===============
  441. /*
  442. lexToken is the main entry function for the lexer.
  443. */
  444. func lexToken(l *lexer) lexFunc {
  445. // Check if we got a quoted value or a comment
  446. n1 := l.next(1)
  447. n2 := l.next(2)
  448. // Parse comments
  449. if (n1 == '/' && n2 == '*') || n1 == '#' {
  450. return lexComment
  451. }
  452. // Parse strings
  453. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  454. return lexValue
  455. }
  456. // Lex a block of text and emit any found tokens
  457. l.startNew()
  458. // First try to parse a number
  459. lexNumberBlock(l)
  460. identifierCandidate := l.input[l.start:l.pos]
  461. keywordCandidate := strings.ToLower(identifierCandidate)
  462. // Check for number
  463. if numberPattern.MatchString(keywordCandidate) {
  464. _, err := strconv.ParseFloat(keywordCandidate, 64)
  465. if err == nil {
  466. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false, false)
  467. return lexToken
  468. }
  469. }
  470. if len(keywordCandidate) > 0 {
  471. l.backup(l.pos - l.start)
  472. }
  473. lexTextBlock(l, true)
  474. identifierCandidate = l.input[l.start:l.pos]
  475. keywordCandidate = strings.ToLower(identifierCandidate)
  476. // Check for keyword
  477. token, ok := KeywordMap[keywordCandidate]
  478. if !ok {
  479. // Check for symbol
  480. token, ok = SymbolMap[keywordCandidate]
  481. }
  482. if ok {
  483. // A known token was found
  484. l.emitToken(token)
  485. } else {
  486. if !NamePattern.MatchString(keywordCandidate) {
  487. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  488. return nil
  489. }
  490. // An identifier was found
  491. l.emitTokenAndValue(TokenIDENTIFIER, identifierCandidate, true, false)
  492. }
  493. return lexToken
  494. }
  495. /*
  496. lexValue lexes a string value.
  497. Values can be declared in different ways:
  498. ' ... ' or " ... "
  499. Characters are parsed between quotes (escape sequences are interpreted)
  500. r' ... ' or r" ... "
  501. Characters are parsed plain between quote
  502. */
  503. func lexValue(l *lexer) lexFunc {
  504. var endToken rune
  505. l.startNew()
  506. allowEscapes := false
  507. r := l.next(0)
  508. // Check if we have a raw quoted string
  509. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  510. endToken = q
  511. l.next(0)
  512. } else {
  513. allowEscapes = true
  514. endToken = r
  515. }
  516. r = l.next(0)
  517. rprev := ' '
  518. lLine := l.line
  519. lLastnl := l.lastnl
  520. for (!allowEscapes && r != endToken) ||
  521. (allowEscapes && (r != endToken || rprev == '\\')) {
  522. if r == '\n' {
  523. lLine++
  524. lLastnl = l.pos
  525. }
  526. rprev = r
  527. r = l.next(0)
  528. if r == RuneEOF {
  529. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  530. return nil
  531. }
  532. }
  533. if allowEscapes {
  534. val := l.input[l.start+1 : l.pos-1]
  535. // Interpret escape sequences right away
  536. if endToken == '\'' {
  537. // Escape double quotes in a single quoted string
  538. val = strings.Replace(val, "\"", "\\\"", -1)
  539. }
  540. s, err := strconv.Unquote("\"" + val + "\"")
  541. if err != nil {
  542. l.emitError(err.Error() + " while parsing string")
  543. return nil
  544. }
  545. l.emitTokenAndValue(TokenSTRING, s, false, true)
  546. } else {
  547. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], false, false)
  548. }
  549. // Set newline
  550. l.line = lLine
  551. l.lastnl = lLastnl
  552. return lexToken
  553. }
  554. /*
  555. lexComment lexes comments.
  556. */
  557. func lexComment(l *lexer) lexFunc {
  558. // Consume initial /*
  559. r := l.next(0)
  560. if r == '#' {
  561. l.startNew()
  562. for r != '\n' && r != RuneEOF {
  563. r = l.next(0)
  564. }
  565. l.emitTokenAndValue(TokenPOSTCOMMENT, l.input[l.start:l.pos], false, false)
  566. if r == RuneEOF {
  567. return nil
  568. }
  569. l.line++
  570. } else {
  571. l.next(0)
  572. lLine := l.line
  573. lLastnl := l.lastnl
  574. l.startNew()
  575. r = l.next(0)
  576. for r != '*' || l.next(1) != '/' {
  577. if r == '\n' {
  578. lLine++
  579. lLastnl = l.pos
  580. }
  581. r = l.next(0)
  582. if r == RuneEOF {
  583. l.emitError("Unexpected end while reading comment")
  584. return nil
  585. }
  586. }
  587. l.emitTokenAndValue(TokenPRECOMMENT, l.input[l.start:l.pos-1], false, false)
  588. // Consume final /
  589. l.next(0)
  590. // Set newline
  591. l.line = lLine
  592. l.lastnl = lLastnl
  593. }
  594. return lexToken
  595. }